AcWing 97. 约数之和
原题链接
中等
作者:
静静在Coding
,
2022-03-24 16:26:34
,
所有人可见
,
阅读 169
题解解析
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod = 9901;
int qmi(int p,int k)
{
LL res = 1;
while(k){
if(k&1) res = res*p%mod;
p =(LL)p*p%mod;
k >>= 1;
}
return res;
}
int sum(int p,int k)
{
if(k == 0) return 1;
if(k & 1) return (1 + qmi(p,k/2 + 1))*sum(p,k/2)%mod;
else return (qmi(p,k) + sum(p,k - 1))%mod;
}
int main()
{
int a,b;
cin>>a>>b;
LL res = 1;
for(int i = 2;i <= a/i;i++){
if(a % i == 0){
int s = 0;
while(a % i == 0){
s++;
a /= i;
}
res = (LL)res * sum(i,s*b)%mod;
}
}
if(a > 1) res = (LL) res * sum(a,b)%mod;
if(a == 0) res = 0;
cout<<res;
return 0;
}