求助一个小细节

P1593 因子和

Noble_Wolf @ 2023-08-30 20:10:43

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define debug cout<<"DS"<<endl
int re(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(int x){
     if(x<0)putchar('-'),x=-x;
     if(x>9)write(x/10);
     putchar(x%10+'0');
}
unordered_map<ll,ll>h;
ll Pow(ll a,ll b,ll p){
    ll res=1;
    while(b){
        if(b&1)res=res*a%p;
        b>>=1;
        a=a*a%p;
    }
    return res;
}
int main(){
    ll a=re();
    ll b=re(),res=a,MOD=9901;
    for(int i=2;i<=res/i;i++){
        while(res%i==0){
            res/=i;
            h[i]++;
        }
    }
    if(res>1)h[res]++;
    ll ans=1;
    for(auto i:h){
        ll p=i.first;
        ll ai=i.second*b+1;
        ll now;
        if(p%MOD==1)now=ai;
        else now = (Pow(p,ai,MOD)-1)*Pow(p-1,MOD-2,MOD)%MOD;
        ans=(ans*now)%MOD;
    }
    cout<<(ans+MOD)%MOD<<endl;
    return 0;
}

这段代码最后一段

    cout<<(ans+MOD)%MOD<<endl;

改成

    cout<<ans<<endl;

就WA 一个点,为什么ans会是负数?


by Withershine @ 2023-08-30 20:39:52

如果 pmod 结果为 0,快速幂会返回 0,这样 (Pow(p,ai,MOD)-1) 的结果就是 -1


|