快速幂

package main

import (
   "fmt"
   "math/big"
)

func main() {
   var q int
   var a int
   var b int
   var p int
   fmt.Scanf("%d\n", &q)
   for i := 0; i < q; i++ {
      fmt.Scanf("%d %d %d\n", &a, &b, &p)
      fmt.Println(getMod(a, b, p))
   }
}
func getMod(a int, b int, p int) int {
   if b == 0 {
      return 1 % p
   }
   t := big.NewInt(1)
   A := big.NewInt(int64(a))
   P := big.NewInt(int64(p))
   for b != 0 {
      if b&1 == 1 {
         t = t.Mul(t, A)
      }
      b >>= 1
      A = A.Mul(A, A)
   }
   mod := t.Mod(t, P)
   return int(mod.Int64())
}