题目链接：http://poj.org/problem?id=1845
关于质因数分解，模板见：http://www.cnblogs.com/atmacmer/p/5285810.html
二分法思想：选定一个要进行比较的目标，在区间[l,r]之间不断二分，直到取到与目标相等的值。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=10000;
const int MOD=9901; ll mult_mod(ll a,ll b)
{
a%=MOD;b%=MOD;
ll res=0;
while(b)
{
if(b&1)
{
res+=a;
res%=MOD;
}
a<<=1;
if(a>=MOD) a%=MOD;
b>>=1;
}
return res;
} ll pow_mod(ll x,ll n)
{
if(n==1) return x%MOD;
x%=MOD;
ll t=x,res=1;
while(n)
{
if(n&1) res=mult_mod(res,t);
t=mult_mod(t,t);
n>>=1;
}
return res;
} int prime[N+5];
int tot;
int vis[N+5]; void isPrime()
{
tot=0;
memset(vis,0,sizeof(vis));
memset(prime,0,sizeof(prime));
for(int i=2;i<=N;i++)
{
if(!vis[i])
{
prime[tot++]=i;
for(int j=i*i;j<N;j+=i)
vis[j]=1;
}
}
} ll factor[100][2];
int cnt;
//分解质因数
void getFactor(ll x)
{
cnt=0;
ll t=x;
for(int i=0;prime[i]<=t/prime[i];i++)
{
factor[cnt][1]=0;
while(t%prime[i]==0)
{
factor[cnt][0]=prime[i];
while(t%prime[i]==0)
{
factor[cnt][1]++;
t/=prime[i];
}
cnt++;
}
}
if(t!=1)
{
factor[cnt][0]=t;
factor[cnt][1]=1;
cnt++;
}
} ll sum(ll p,ll n)
{
if(p==0) return 0;
if(n==0) return 1;
if(n&1)
return ((1+pow_mod(p,n/2+1))%MOD*sum(p,n/2)%MOD)%MOD;
else
return ((1+pow_mod(p,n/2+1))%MOD*sum(p,n/2-1)+pow_mod(p,n/2)%MOD)%MOD;
} int main()
{
int a,b;
isPrime();
while(~scanf("%d%d",&a,&b))
{
getFactor(a);
ll ans=1;
for(int i=0;i<cnt;i++)
{
ans*=(sum(factor[i][0],b*factor[i][1])%MOD);
ans%=MOD;
}
printf("%I64d\n",ans);
}
return 0;
}