萌新求助为什么需要注意负数

P1593 因子和

剑客红尘 @ 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


|