题目描述
注意:python的整除是 //
样例
def qmi(a, b, p):
res = 1
while b:
if b & 1:
res = res * a % p
a = a * a % p
b >>= 1
return res
def c(a, b, p):
res = 1
i, j = 1, a
while i <= b:
res = res * j % p
res = res * qmi(i, p-2, p) % p
j -= 1
i += 1
return res
def lacus(a, b, p):
if a < p and b < p:
return c(a, b, p)
return c(a % p, b % p, p) * lacus(a // p, b // p, p) % p # python 整除是//
if __name__ == "__main__":
n = int(input())
for _ in range(n):
a, b, p = map(int, input().split())
print(int(lacus(a, b, p)))
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla