数论求a^b(a,b为1e12级别）的因子之和

1.首先考虑将a质因子分解，筛出1e6内的a的质因子及幂次，若a还有质因子（未被筛成1的话）则有一个大于1e6的大质因子（至多一个）（补上即找到所有质因子）

2.将b放入幂指数

3.考虑一个生成函数

a^b的因子之和=(p1^0+p1^1.....+p1^k1)(p2^0+.....+p2^k2).....(pm^0+...pm^km)

这个生成函数的每一项都是一个不同的因子（此处p为a的质因子）

4.最后就是处理一系列等比数列的和，方法一是等比求和，但由于mod过小 有可能出现q为1的情况 ，此时要回到求和（个别），其余正常求

方法二是直接递归log求等比数列连续和（模版如下）

（注意qmul防乘法溢出（大于1e9容易））

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxx=1000006;
const int mod=9901;
int pri[maxx];
bool ispri[maxx];
int cnt;
long long cc[maxx];
void prime()
{
	cnt=1;
	memset(ispri,1,sizeof(ispri));
	ispri[0]=ispri[1]=0;
	for(int i=2;i<=maxx;++i)
	{
		if(ispri[i])
		pri[cnt++]=i;
		for(int j=1;j<cnt&&pri[j]*i<maxx;++j)
		{
			ispri[pri[j]*i]=0;
			if(i%pri[j]==0)
			break;
		}
	}
}
ll qmul(ll a,ll b)
{
	ll ans=0;
	while(b)
	{
		if(b&1)
		ans=(ans+a)%mod;
		a=(a+a)%mod;
		b>>=1;
	}
	return ans;
}
ll qpow(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		ans=qmul(ans,a);
		a=qmul(a,a);
		b>>=1;
	}
	return ans;
}
ll m(ll x)
{
	return qpow(x,mod-2);
}
ll work(ll a,ll b)
{
	if(b==0ll) return 1ll;
	if(b==1ll) return (1+a)%mod;
	if(b%2==0) return ((1ll+qpow(a,b/2))%mod*work(a,(b-1)/2)%mod*a%mod+1ll)%mod;
	return (1ll+qpow(a,(b+1ll)/2))%mod*work(a,b/2)%mod;
}
int main ()
{
	freopen("spring.in","r",stdin);
	freopen("spring.out","w",stdout);
	ll a,b;
	cin>>a>>b;
	prime();
	--cnt;
	long long k;
	int maxx;
	for(int i=1;i<=cnt;++i)
	{
		if(a%pri[i]==0)
		{
			maxx=i;
			cc[i]=1;
			a/=pri[i];
		    while(1)
		  {
			if(a%pri[i]==0)
			{
				cc[i]++;
			a/=pri[i];
			}
			else break;
		  }
		}
		cc[i]*=b;
	}
	ll ans=1;
	for(int i=1;i<=maxx;++i)
	{
		if(cc[i])
		ans=(ans*work(pri[i],cc[i]))%mod;
	}
	if(a>1)
	ans=(ans*work(a,b))%mod;
	cout<<ans;
	return 0;
}