信息学奥赛一本通 1633：【例 3】Sumdiv | OpenJudge 百练 1845:Sumdiv
【题目链接】
ybt 1633：【例 3】Sumdiv
OpenJudge 百练 1845:Sumdiv
【题目考点】
1. 乘法逆元
当模数p pp为质数时，可以使用快速幂求逆元
a − 1 m o d p = a p − 2 m o d p a^{-1} \bmod p =a^{p-2} \bmod pa−1modp=ap−2modp
2. 算术基本定理（分解质因数）
对n nn分解质因数，得n = p 1 a 1 p 2 a 2 . . . p n a n n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}n=p1a1p2a2...pnan
那么n nn的约数和为：( 1 + p 1 + . . . + p 1 a 1 ) ( 1 + p 2 + . . . + p 2 a 2 ) . . . ( 1 + p n + . . . + p n a n ) (1+p_1+...+p_1^{a_1})(1+p_2+...+p_2^{a_2})...(1+p_n+...+p_n^{a_n})(1+p1+...+p1a1)(1+p2+...+p2a2)...(1+pn+...+pnan)
3. 等比数列求和
等比数列求和公式：S = a 1 ( q n − 1 ) q − 1 S=\frac{a_1(q^n-1)}{q-1}S=q−1a1(qn−1)，其中a 1 a_1a1为首项，q qq为公比，n nn为项数
4. 费马小定理
g c d ( a , p ) = 1 gcd(a,p)=1gcd(a,p)=1,p pp为质数时：a p − 1 ≡ 1 ( m o d p ) a^{p-1}\equiv 1 \pmod pap−1≡1(modp)，
推论g c d ( a , p ) = 1 gcd(a,p)=1gcd(a,p)=1,p pp为质数时：a b ≡ a b m o d ( p − 1 ) ( m o d p ) a^b\equiv a^{b \bmod (p-1)} \pmod pab≡abmod(p−1)(modp)，p pp为质数。
【解题思路】
首先手写质数判断函数，判断确定9901为质数，设M = 9901 M=9901M=9901
对A AA分解质因数，得：A = p 1 a 1 p 2 a 2 . . . p n a n A=p_1^{a_1}p_2^{a_2}...p_n^{a_n}A=p1a1p2a2...pnan
那么A B = p 1 a 1 B p 2 a 2 B . . . p n a n B A^B=p_1^{a_1B}p_2^{a_2B}...p_n^{a_nB}AB=p1a1Bp2a2B...pnanB
A B A^BAB的约数和为S SS。
S = ( 1 + p 1 + . . . + p 1 a 1 B ) ( 1 + p 2 + . . . + p 2 a 2 B ) . . . ( 1 + p n + . . . + p n a n B ) S=(1+p_1+...+p_1^{a_1B})(1+p_2+...+p_2^{a_2B})...(1+p_n+...+p_n^{a_nB})S=(1+p1+...+p1a1B)(1+p2+...+p2a2B)...(1+pn+...+pnanB)
对于其中的一项1 + p k + . . . + p k a k B 1+p_k+...+p_k^{a_kB}1+pk+...+pkakB
设p m = p k m o d M p_m=p_k\bmod Mpm=pkmodM
- 如果M ∣ p k M\mid p_kM∣pk，则p m = 0 p_m=0pm=0
( 1 + p k + . . . + p k a k B ) m o d M = ( 1 + p m + p m 2 + . . . + p m a k B ) m o d M = 1 (1+p_k+...+p_k^{a_kB})\bmod M=(1+p_m+p_m^2+...+p_m^{a_kB})\bmod M=1(1+pk+...+pkakB)modM=(1+pm+pm2+...+pmakB)modM=1 - 如果M ∣ ( p k − 1 ) M\mid (p_k-1)M∣(pk−1)，则p m = 1 p_m=1pm=1，
( 1 + p k + . . . + p k a k B ) m o d M = ( 1 + 1 + 1 2 + . . . + 1 a k B ) = a k B + 1 (1+p_k+...+p_k^{a_kB})\bmod M=(1+1+1^2+...+1^{a_kB})=a_kB+1(1+pk+...+pkakB)modM=(1+1+12+...+1akB)=akB+1 - 其它情况时
有M ∤ p k M\nmid p_kM∤pk，即g c d ( M , p k ) = g c d ( M , p k m o d M ) = g c d ( M , p m ) = 1 gcd(M, p_k) = gcd(M, p_k \bmod M)=gcd(M, p_m)=1gcd(M,pk)=gcd(M,pkmodM)=gcd(M,pm)=1。
有M ∤ ( p k − 1 ) M\nmid (p_k-1)M∤(pk−1)，即g c d ( M , p k − 1 ) = g c d ( M , ( p k − 1 ) m o d M ) = g c d ( M , p m − 1 ) = 1 gcd(M, p_k-1) = gcd(M, (p_k-1)\bmod M) = gcd(M, p_m-1)=1gcd(M,pk−1)=gcd(M,(pk−1)modM)=gcd(M,pm−1)=1。
设S k = 1 + p k + . . . + p k a k B S_k=1+p_k+...+p_k^{a_kB}Sk=1+pk+...+pkakB
求S k m o d M = ( 1 + p m + . . . + p m a k B ) m o d M S_k \bmod M=(1+p_m+...+p_m^{a_kB}) \bmod MSkmodM=(1+pm+...+pmakB)modM
使用等比数列求和公式，得：
S k = p m a k B + 1 − 1 p m − 1 m o d M S_k=\dfrac{p_m^{a_kB+1}-1}{p_m-1}\bmod MSk=pm−1pmakB+1−1modM- 对于S k S_kSk的分子，求( p m a k B + 1 − 1 ) m o d M = ( p m a k B + 1 m o d M − 1 ) m o d M (p_m^{a_kB+1}-1) \bmod M=(p_m^{a_kB+1}\bmod M-1) \bmod M(pmakB+1−1)modM=(pmakB+1modM−1)modM
模数M MM为质数，且g c d ( M , p m ) = 1 gcd(M,p_m)=1gcd(M,pm)=1，根据费马小定理，可以进行降幂处理：
p m a k B + 1 m o d M = p m ( a k B + 1 ) m o d ( M − 1 ) m o d M p_m^{a_kB+1}\bmod M=p_m^{(a_kB+1)\bmod (M-1)}\bmod MpmakB+1modM=pm(akB+1)mod(M−1)modM。该式可以使用快速幂取模算法求解。 - 对于S k S_kSk分母中的一项1 p m − 1 m o d M \dfrac{1}{p_m-1} \bmod Mpm−11modM，已知g c d ( p m − 1 , M ) = 1 gcd(p_m-1, M) = 1gcd(pm−1,M)=1,可以求p m − 1 p_m-1pm−1模M MM的逆元，即( p m − 1 ) − 1 m o d M (p_m-1)^{-1} \bmod M(pm−1)−1modM。
由于模数M MM为质数，可以使用快速幂求乘法逆元：( p m − 1 ) − 1 m o d M = ( p m − 1 ) M − 2 m o d M (p_m-1)^{-1} \bmod M=(p_m-1)^{M-2} \bmod M(pm−1)−1modM=(pm−1)M−2modM
- 对于S k S_kSk的分子，求( p m a k B + 1 − 1 ) m o d M = ( p m a k B + 1 m o d M − 1 ) m o d M (p_m^{a_kB+1}-1) \bmod M=(p_m^{a_kB+1}\bmod M-1) \bmod M(pmakB+1−1)modM=(pmakB+1modM−1)modM
因此S k = ( p m ( a k B + 1 ) m o d ( M − 1 ) − 1 ) ( p m − 1 ) M − 2 m o d M S_k=(p_m^{(a_kB+1)\bmod (M-1)}-1)(p_m-1)^{M-2}\bmod MSk=(pm(akB+1)mod(M−1)−1)(pm−1)M−2modM
遍历A AA的所有质因数p k p_kpk，求出各个S k S_kSk的值，结果相乘并模M，得到最终结果。
【题解代码】
解法1：
#include<bits/stdc++.h>usingnamespacestd;#defineM9901#defineMOD(a,b)(((a)%(b)+(b))%(b))typedeflonglongLL;LL A,B,ans=1;map<LL,LL>f;//i是一个质因数，f[i]是i的指数voidinitFac(LL n){for(LL i=2;i*i<=n;++i)while(n%i==0){f[i]++;n/=i;}if(n>1)f[n]=1;}LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}LLsolve(LL p,LL a)//对于A中的一项质因数p^a，求出S=1+p+...+p^aB{LL pm=p%M;if(pm==0)return1;elseif(pm==1)return(a*B+1)%M;else{LL fz=MOD(fastPow(pm,(a*B+1)%(M-1),M)-1,M);LL fm=fastPow(pm-1,M-2,M);returnMOD(fz*fm,M);}}intmain(){cin>>A>>B;if(A==0){cout<<0;return0;}if(A==1){cout<<1;return0;}initFac(A);for(pair<LL,LL>pa:f)ans=MOD(ans*solve(pa.first,pa.second),M);cout<<ans;return0;}