POJ-1845 Sumdiv (基础数论综合)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod=9901;
ll p,bk[5005],sum[5005],q[5005];
void fj(ll x)
{
	p=0;
	memset(sum,0,sizeof(sum));
	for(int i=2;i*i<=x+1;i++)
	{
		if(x%i==0)
		{
			q[++p]=i;
			while(x%i==0)
			sum[p]++,x/=i;
		}
	}
	if(x>1)
	q[++p]=x,sum[p]=1;
}
ll qpow(ll a,ll b)
{
	ll ans=1;
	ll base=a;
	while(b)
	{
		if(b&1)
		ans=ans%mod*base%mod,ans%=mod;
		base=base%mod*base%mod,base%=mod;
		b>>=1;
	}
	return ans%mod;
}
ll getsum(ll a,ll b)
{
	if(b==0)
	return 1;
	if(b%2==1) //奇数式
	return ((1+qpow(a,(b+1)/2))*getsum(a,(b-1)/2)%mod)%mod;
	if(b%2==0) //偶数式
	return ((1+qpow(a,b/2))*getsum(a,(b/2)-1)%mod+qpow(a,b))%mod;
}
int main()
{
	ll n,m,ans=0;
	while(~scanf("%lld%lld",&n,&m))
	{
		fj(n);
		ans=1;
		for(int i=1;i<=p;i++)
		{
			ans=ans%mod*(getsum(q[i],sum[i]*m))%mod;
			ans%=mod;
		}
		printf("%lld\n",ans%mod);
	}
}