[poj1845] sumdiv [number theory]

$link$

analysis ：

Consider the unique decomposition theorem $A$ It can be expressed as ${\prod }_{i=1}^n{p}_i^{c_i}$
The sum of divisors is $(1+p_1+p_1^2+...+p_1^{c_1})\times (1+p_2+p_2^2+...+p_2^{c_2})\times ...\times (1+p_n+p_n^2+...+p_n^{c_n})$

that $A^B$ Can be expressed as ${\prod }_{i=1}^n{p}_i^{c_i\times B}$
At this time, the sum of the divisors is $(1+p_1+p_1^2+...+p_1^{c_1\times B})\times (1+p_2+p_2^2+...+p_2^{c_2\times B})\times ...\times (1+p_n+p_n^2+...+p_n^{c_n\times B})$
Each part can be summed by an equal ratio sequence namely ${\prod }_{i=1}^n\frac{p_i^{c_i+1}-1}{p_i-1}$ So fast power multiplication $p_i-1$ The inverse element of

be aware $9901$ Prime number if $p_i-1$ yes $9901$ Multiple The inverse element will not exist here $p_i\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}9901)$
So the sum of the equal ratio series is $(1+1+1^2+...+1^{c_n\times B+1})=c_n\times B+1$ The answer is ${\prod }_{i=1}^n{c}_i\times B+1$

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define reg register
using namespace std;
typedef long long ll;
const ll Mod=9901,N=1e5+5;
ll A,B,p[N],c[N],tot,ans=1;
void calc(ll x)
{
    
	for(int i=2;i*i<=x;i++)
	{
    
		if(x%i==0)
		{
    
			p[++tot]=i;
			c[tot]=1;
			x/=i;
			while(x%i==0)
				x/=i,c[tot]++;
		}
	}
	if(x>1) p[++tot]=x,c[tot]=1;
}
ll ksm(ll a,ll k)
{
    
	ll res=1;
	while(k)
	{
    
		if(k&1) (res*=a)%=Mod;
		(a*=a)%=Mod;
		k>>=1;
	}
	return res;
}
int main(){
    
	scanf("%lld%lld",&A,&B);
	calc(A);
	for(int i=1;i<=tot;i++)
	{
    
		int a=p[i],k=B*c[i];
		((a-1)%Mod==0)?ans=ans%Mod*(k+1)%Mod:ans=ans%Mod*(ksm(a,k+1)%Mod-1+Mod)%Mod*ksm(a-1,Mod-2)%Mod;
	}
	printf("%lld",ans);
	return 0;
}