题目描述
求\(A^B\)的所有约数之和\(mod\mbox{ 9901 } (1≤A,B≤5*10^7)\)
输入
2 3
输出
15
题解
(1) 整数的唯一分解定理:
任意正整数都有且只有一种方式写出其素因子的乘积表达式。
\(A=(p1^{k1})*(p2^{k2})*(p3^{k3})*....*(pn^{kn})\)其中\(pi\)均为素数(2) 约数和公式:
对于已经分解的整数\(A=(p1^{k1})*(p2^{k2})*(p3^{k3})*....*(pn^{kn})\)
有A的所有因子之和为
\[ S = (1+p1+p1^2+...p1^{k1}) * (1+p2+p2^2+….p2^{k2}) * .... *\] \[(1+pn+pn^2+pn^3+...pn^{kn})\]
(3) 费马小定理求逆元: \[a^{-1} \equiv a^{P-2} \mbox{ ( mod P ) }\] (4) 求等比数列: \[(1+p1+p1^2+...p1^{B*k1})=\frac{p1^{B*k1+1}-1}{p1-1}\] 特别的,若 \(p1-1\) 是9901的倍数有 \(p1 \equiv 1 \mbox{ ( mod P ) }\) 所以有,\[(1+p1+p1^2+...p1^{B*k1})\equiv B*k1+1\mbox{ ( mod P ) }\]code
#include#include #define re register int#define int long longusing namespace std;inline void read(int &x){ x=0;char ch=getchar(); for(;!isdigit(ch);ch=getchar()); for(; isdigit(ch);ch=getchar()) x=(x<<1)+(x<<3)+(ch^48);}const int N=300,P=9901;int p[N],c[N],a,b,ans=1,t,inv[100000];inline void get(){ inv[1]=1; for(re i=2;i<100000;++i) inv[i]=((P-P/i)*inv[P%i])%P;}inline int ksm(int x,int y){ int res=1; for(;y;y>>=1,x=x*x%P) if(y&1) (res*=x)%=P; return res%P;}signed main(){ get(); while(scanf("%lld%lld",&a,&b)!=EOF){ t=0,ans=1; for(re i=2;i*i<=a;++i) if(a%i==0) { p[++t]=i,c[t]=0; while(a%i==0) a/=i,++c[t]; } if(a>1) p[++t]=a,c[t]=1; for(re i=1;i<=t;++i){ if((p[i]-1)%P==0) (ans*=(b*c[i]+1)%P)%=P; //没有逆元时特判 else (ans*=((ksm(p[i],c[i]*b+1)-1+P)*ksm(p[i]-1,P-2)%P))%=P; //ksm(p[i],c[i]*b+1)-1+P ,记得取模减法后%P+P再%P, //调这个用了1h+ } printf("%lld\n",ans%P); }return 0;}