2961. 双模幂运算

双模幂运算

• 难度: medium
• 原始链接: https://leetcode.cn/problems/double-modular-exponentiation
• 标签: 快速幂

解法一: 快速幂

go

func getGoodIndices(variables [][]int, target int) []int {
  ans := []int{}
  for i, variable := range variables {
    a := variable[0]
    b := variable[1]
    c := variable[2]
    m := variable[3]
    if quickPow(quickPow(a, b, 10), c, m) == target {
      ans = append(ans, i)
    }
  }
  return ans
}

func quickPow(num, pow, mod int) int {
  if pow == 0 {
    return 1
  }
  half := quickPow(num, pow>>1, mod)
  if (pow & 1) == 0 {
    return (half * half) % mod
  }
  return (half * half * num) % mod
}