97. 约数之和【Python实现】
Date:3.27
Key:质因子分解、逆元、快速幂
思路
对A进行质因子分解:
$$
A=\prod_{i=1}^m p_i^{k_i}
$$
则:
$$
A^B=\prod_{i=1}^m p_i^{k_i*B}
$$
根据约数之和定理:
$$
S=\prod_{i=1}^m(p_i^0+p_i^1+p_i^2+…+p_i^{B*k_i})
$$
很显然,对于每一项,可以采用等比数列求和的公式来算:
$$
S=\prod_{i=1}^m\frac{p_i^{B*k_i+1}-1}{p_i-1}
$$
这里,出现了除法运算,考虑用逆元的时候,因为9901是一个比较小的素数,所以会出现如下两种情况:
(1)如果$(p_i-1)%m!=0$,则直接用逆元来做即可
(2)如果$(p_i-1)%m=0$,不可以用逆元做,进行如下推导
$$
令t=p_i-1,\quad t\%9901=0\\
\frac{p_i^{B*k_i+1}-1}{p_i-1}\\
=\frac{(t+1)^{B*k_i+1}-1}{t}\\
=\frac{C_{B*k_i+1}^{B*k_i+1}*t^(B*k_i+1)+…+C_{B*k_i+1}^0-1}{t}
$$
此式将分子分母中的t消掉之后,对9901取模,即为$(C_{B*k_i+1}^1\%9901)$
最后,编程实现如下
代码
from math import sqrt
a,b = map(int, input().split())
mod = 9901
def ksm(x, y):
res = 1
while y:
if y & 1:
res = res * x % mod
x = x * x % mod
y >>= 1
return res
def solve():
global a, b
if a == 0: print(0);return
if b == 0: print(1);return
ans = 1
for pi in range(2, int(sqrt(a)) + 1):
if a % pi == 0:
ki = 0
while a % pi == 0:
ki += 1
a //= pi
if (pi - 1) % mod == 0:
ans = (ans * (b * ki) % mod) % mod
else:
fz = ksm(pi, b * ki + 1) - 1
fm = ksm(pi - 1, mod - 2)
ans = (ans * (fz * fm) % mod) % mod
if a > 1:
if (a - 1) % mod == 0:
ans = (ans * b % mod) % mod
else:
fz = ksm(a, b + 1) - 1
fm = ksm(a - 1, mod - 2)
ans = (ans * (fz * fm) % mod) % mod
print(ans)
solve()