题意：求a^b的所有约数之和mod9901。
思路：因为一个数A能够表示成多个素数的幂相乘的形式。即A=(a1^n1)*(a2^n2)*(a3^n3)...(am^nm)。所以这个题就是要求
(1+a1+a1^2+...a1^n1)*(1+a2+a2^2+...a2^n2)*(1+a3+a3^2+...a3^n2)*...(1+am+am^2+...am^nm) mod 9901。
对于每一个(1+a1+a1^2+...a1^n1) mod 9901
等于 (a1^(n1+1)-1)/(a1-1) mod 9901，这里用到逆元的知识：a/b mod c = (a mod (b*c))/ b
所以就等于(a1^(n1+1)-1)mod (9901*(a1-1)) / (a1-1)。
至于前面的a1^(n1+1)，快速幂。
#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<map> #include<queue> #include<cmath> #define ll long long using namespace std; int a,b,m,ans=1,mod=9901; int p[20],c[20]; void devide(int n) { m=0; for(int i=2;i*i<=n;i++) { if(n%i==0) { p[++m]=i; c[m]=0; while(n%i==0) { n/=i; c[m]++; } } } if(n>1) p[++m]=n,c[m]=1; } int power(int a,ll b) { int c=1; for(;b;b>>=1) { if(b&1) c=(ll)c*a%mod; a=(ll)a*a%mod; } return c; } int main() { scanf("%d%d",&a,&b); devide(a); for(int i=1;i<=m;i++) { if((p[i]-1)%mod==0) { ans=((ll)b*c[i]+1)%mod*ans%mod; continue; } int x=pow(p[i],(ll)b*c[i]+1); x=(x-1+mod)%mod; int y=p[i]-1; y=power(y,mod-2); ans=(ll)ans*x%mod*y%mod; } printf("%d ",ans); }