萌新求助为什么需要注意负数
查看原帖
萌新求助为什么需要注意负数
362542
剑客红尘楼主2023/1/7 17:20

以下的我的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;
}

2023/1/7 17:20
加载中...