bigmod 函数 returns 负值

Question

long long int big_mod(long long int base, long long int power, long long int mod)
{
    if(power==0)    return 1;
    else if(power%2==1)
    {
        int p1 = base % mod;
        int p2 = (big_mod(base,power-1,mod))%mod;
        return (p1*p2)%mod;
    }
    else if(power%2==0)
    {
        int p1 = (big_mod(base,power/2,mod))%mod;
        return (p1*p1)%mod;
    }
}

此函数 returns (3 140068687 419634856) 输入的负值。为什么会这样？谁能解释一下。

Answer 1

returning 的值可能太大（p1*p2 和p1*p1），它会使您的程序溢出。

使用(A * B) mod C = (A mod C * B mod C) mod C计算模数

因此您可以更改 return 值：

else if(power%2==1)
{
     ...
     return ((p1%mod) * (p2%mod))%mod;
}
else if(power%2==0)
{
     ...
     return ((p1%mod) * (p1%mod))%mod;
}

bigmod 函数 returns 负值

bigmod function returns negative value

c

bigmod