信息学奥赛一本通 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=p1a1​​p2a2​​...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=p1a1​​p2a2​​...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=p1a1​B​p2a2​B​...pnan​B​
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​+...+p1a1​B​)(1+p2​+...+p2a2​B​)...(1+pn​+...+pnan​B​)
对于其中的一项1 + p k + . . . + p k a k B 1+p_k+...+p_k^{a_kB}1+pk​+...+pkak​B​
设p m = p k m o d M p_m=p_k\bmod Mpm​=pk​modM

• 如果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​+...+pkak​B​)modM=(1+pm​+pm2​+...+pmak​B​)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​+...+pkak​B​)modM=(1+1+12+...+1ak​B)=ak​B+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,pk​modM)=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​+...+pkak​B​
  求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 MSk​modM=(1+pm​+...+pmak​B​)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​−1pmak​B+1​−1​modM
  • 对于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(pmak​B+1​−1)modM=(pmak​B+1​modM−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 Mpmak​B+1​modM=pm(ak​B+1)mod(M−1)​modM。该式可以使用快速幂取模算法求解。
  • 对于S k S_kSk​分母中的一项1 p m − 1 m o d M \dfrac{1}{p_m-1} \bmod Mpm​−11​modM，已知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 = ( 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(ak​B+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;}