摘要
Title: 875. 快速幂
Tag: 快速幂
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

875. 快速幂

• 题意

  给定 n 组 ai,bi,pi，对于每组数据，求出 ai^bi mod pi 的值。

• 思路

  将b(幂)拆成若干个2的次幂相加，其实就是看b的二进制表示里，哪些是1，就乘上它

• 代码

  def qpow(a, b, p):
      res = 1
      while b:
          if b & 1:
              res = res * a % p
          b >>= 1
          a = a * a % p
      return res
  
  
  for _ in range(int(input())):
      a, b, p = map(int, input().split())
      print(qpow(a, b, p))
      # print(pow(a, b, p))