由題意，要求A^B的所有約數(shù)之和%9901。
A可以唯一分解成p1^a1*p2^a2*...*pn^an,
A^B=p1^(a1*B)*p2^(a2*B)*...*pn^(an*B);
A^B的所有約數(shù)之和=[1+p1+p1^2+...+p1^(a1*B)]*[1+p2+p2^2+...+p2^(a2*B)]*[1+pn+pn^2+...+pn^(an*B)].
而等比數(shù)列1+pi+pi^2+pi^3+...+pi^n可以由二分求得，思想是把式子從中間斷開。
若n為奇數(shù)，一共有偶數(shù)項(xiàng)，設(shè)p為3，則(1+p)+(p^2+p^3)=(1+p)+p^2(1+p).
若n為偶數(shù)，一共有奇數(shù)項(xiàng)，設(shè)p為4，則(1+p)+p^2+(p^3+p^4)=(1+p)+p^2+p^3(1+p)。
而p^n可以二分求出。
這樣兩次二分就可以求出了.
CODE
#include<iostream>
#define LL long long
#define M 9901
#define MAX 10000
int A,B;
using namespace std;
int p[MAX],c[MAX];
/*LL pow(LL a,LL n)
{
if(n==0)
return 1;
LL k=pow(a,n/2)%M;
if(n&1)
return (a*k*k%M)%M;
else return (k*k%M);
}*/
LL pow(LL x,LL n)
{
LL ret=1,s=x;
while (true)
{
if (n&1) ret=(ret%M*s%M)%M;
if (n>>=1) s=(s%M*s%M)%M;
else break;
}
return ret;
}
LL sum(LL p,LL n)
{
if(n==0)
return 1;
if(n&1)
return ((1+pow(p,n/2+1))%M*sum(p,n/2)%M)%M;
else
return ((1+pow(p,n/2+1))%M*sum(p,(n-1)/2)%M+pow(p,n/2)%M)%M;
}
int main()
{
cin>>A>>B;
int i,j;
for(i=2;i*i<=A;i++)
{
if(A%i==0)
{
p[++p[0]]=i;
while(A%i==0)
{
A/=i;
c[p[0]]++;
}
}
}
if(A!=1)
{
p[++p[0]]=A;
c[p[0]]=1;
}
LL res=1;
for(i=1;i<=p[0];i++)
{
res=(res%M*sum(p[i],B*c[i])%M)%M;
}
cout<<res<<endl;
system("pause");
return 0;
}