关于第14个点的溢出

P1593 因子和

Xhesika_Frost @ 2021-10-12 09:11:56

本人的快速幂代码如下

int qp(int x,int mi){
    int ans=1;
    int tem=x%mod;
    while(mi){
        if(mi&1){
            ans*=tem;
            ans%=mod;
        }
        tem*=tem;
        tem%=mod;
        mi>>=1;
    }
    return ans;
}

然后本人调用的时候如果这样写就会溢出

ans*=(qp(i,cnt)-1)%mod*(qp(i-1,mod-2))%mod;

如果这样写就不会

ans*=(qp(i%mod,cnt)-1)%mod*(qp(i%mod-1,mod-2))%mod;

这是为什么呢

by Eason_AC @ 2021-10-12 09:27:41

你把下面这一段

if(mi&1){
    ans*=tem;
    ans%=mod;
}
tem*=tem;
tem%=mod;

改写成：

if(mi&1) ans=1ll*ans*tem%mod;
tem=1ll*tem*tem%mod;

看看会不会过？

@SheffieldArchie

by Xhesika_Frost @ 2021-10-12 09:30:51

@Eason_AC 还是会溢出诶

以及我写了

define int long long

by Eason_AC @ 2021-10-12 09:38:57

@SheffieldArchie 那您怎么不早说

by Xhesika_Frost @ 2021-10-12 09:43:55

@Eason_AC 疏忽疏忽对不起对不起 (。・＿・。)ﾉI’m sorry~

by fjy666 @ 2021-10-12 09:51:01

plz don`t at me.

i%mod==0就boom了。