剑客红尘 @ 2023-01-07 17:20:13
以下的我的AC代码,如果我在最后输出只写ans,就会错第13个点,我寻思着这道题不会出现负数啊,为什么需要负数模。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
const LL MOD=9901ll;
LL a,b;
LL sum[N],cnt[N],tot;
LL ans=1;
LL qsm(LL a,LL b){
LL ans=1;
while(b){
if(b&1) ans=ans*a%MOD;
a=a*a%MOD;
b>>=1;
}
return ans;
}
LL Calc(LL num,LL k){
LL res=0;
if((num-1)%MOD==0) res=k+1;
else res=(qsm(num,k+1)-1)*qsm(num-1,MOD-2)%MOD;
return res%MOD;
}
int main(){
cin>>a>>b;
for(int i=2;i*i<=a;i++)
if(a%i==0){
sum[++tot]=i;
while(a%i==0){
cnt[tot]++;
a/=i;
}
}
if(a>1){
sum[++tot]=a;
cnt[tot]=1;
}
for(int i=1;i<=tot;i++) cnt[i]*=b;
for(int i=1;i<=tot;i++) ans=ans*Calc(sum[i],cnt[i])%MOD;
cout<<(ans%MOD+MOD)%MOD;
return 0;
}
by ud2_ @ 2023-01-07 17:26:39
试试输入 9901 1
。