AcWing 97. 约数之和
原题链接
中等
作者:
最后五分钟
,
2024-03-13 21:32:57
,
所有人可见
,
阅读 13
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int mod=9901;
typedef pair<int,int> PII;
int res=1;
int qmi(int a,int k)
{
a%=mod;
int res=1;
while(k)
{
if(k&1)res=(res*a)%mod;//如果这一位存在
a=a*a%mod;
k>>=1;
}
return res;
}
int sum(int a,int k)
{
if(k==0)return 1;
if(k%2)return sum(a,k/2)*(1+qmi(a,(k+1)/2))%mod;
else return (a%mod*sum(a,k-1)+1)%mod;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a,b;
cin>>a>>b;
for(int i=2;i<=a;i++)
{
int s=0;
while(a%i==0)
{
s++;
a/=i;
}
if(s)res=res*sum(i,s*b)%mod;
}
if(!a)res=0;
cout<<res<<endl;
return 0;
}