题意:求A^B的所有因子之和，并对其取模 9901再输出
对于数A=p1^c1+p2^c2+...+pn*cn，它的所有约数之和为(1+p1+p1^2+p1^3+...+p1^(c1*B))*(1+p2+p2^2+p2^3+...+p2^(c2*B))*...*(1+pn+pn^2+pn^3+...+pn^(cn*B))
注意到约数之和的每一项都是等比数列，可以用通项搞他，先用快速幂计算分子，再求出分母的乘法逆元。
特别地，当分母pi-1为9901的倍数时，乘法逆元不存在，但是1,pi,pi^2...pi^(ci*B) ≡ 1 (mod 9901)
所以此时贡献即为B*ci+1 mod 9901
#include<cstdio> #include<iostream> #define ll long long #define R register int using namespace std; const int M=9901; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch==‘-‘?-1:fix; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix; } int a,b,cnt; int p[20],c[20]; ll ans=1; inline void div(int n) { for(R i=2;i*i<=n;++i) if(n%i==0) { p[++cnt]=i; while(n%i==0) n/=i,++c[cnt]; } if(n>1) p[++cnt]=n,c[cnt]=1; } inline int qpow(int a,ll p) { R ret=1; a%=M; for(;p;p>>=1,(a*=a)%=M) if(p&1) ret=(ll)ret*a%M; return ret; } signed main() { a=g(),b=g(); div(a); for(R i=1;i<=cnt;++i) { if((p[i]-1)%M==0) { ans=((ll)b*c[i]+1)%M*ans%M; continue; } R x=(qpow(p[i],(ll)b*c[i]+1)-1+M)%M; R y=qpow(p[i]-1,M-2); ans=(ll)ans*x%M*y%M; } printf("%lld\n",ans); }
2019.05.11
原文：https://www.cnblogs.com/Jackpei/p/10847493.html