c-bigmod函数返回负值

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;
}
}

此函数为(3 140068687 419634856(输入返回负值。为什么会发生这种情况？谁能解释一下吗。

Answer 1

返回的值可能太大(p1*p2和p1*p1(，会使程序溢出。

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

因此，您可以更改返回值：

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