记录编号	593442	评测结果	AAAAAAAAAAAAA
题目名称	[POJ 1845] Sumdiv	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2024-09-01 22:52:12	内存使用	3.34 MiB

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
long long a,b,mod=9901,ans=1,cnt,top,x;
long long get(long long i,long long j){
	long long su=1;
	while(j){
		if(j&1)
		su=(long long)su*i%mod;
		i=i*i%mod; 
		
		j/=2;
	}
	return su;
}
long long sum(long long p,long long c){
	if(c==1)
	return (1+p)%mod;
	if(c==0)
	return 1;
	if(c%2==1){
		return ((long long)(1+get(p,(c+1)/2))*sum(p,(c-1)/2))%mod; 
	}
	else{
		return ((long long)(1+get(p,(c/2)+1))*sum(p,(c/2)-1)+get(p,c/2))%mod;
	}
}
signed main(){
	freopen("sumdiv.in","r",stdin);
    freopen("sumdiv.out","w",stdout);
	long long n;
	cin>>a>>b;
	if(a==0){
		cout<<"0";
		return 0;
	}
	x=a;
	for(long long i=2;i<=a;i++){
		if(x==1)
		break;
		if(x%i==0){
			long long j=i,k=1;
			while(x%j==0){
				j=j*i;
				k++;
			}
			k--;
			j/=i;
			ans=(long long)(ans*sum(i,(long long)k*b))%mod;
			x/=j;
		} 
	}
    cout<<ans;
	return 0;//好习惯
}