为什么我会得到一个负值？

Question

我的代码的幂函数有一些错误，它对小的值返回正确的答案，但对大的值给出错误的答案。

#include<stdio.h>
long long MOD= 1000000007;
long long power(long long i,long long j)
{
        if(j==0)
                return 1;
        long long d;
        d=power(i,j/(long long)2);
        if(j%2==0)
                return (d*d)%MOD;
        else
                return (d*d*i)%MOD;
}

int main()
{
        long long inv=1;
        inv=power(25,MOD-2)%MOD;
        printf("%lld\n",inv);
}

Answer 1

带符号的long long的范围是-2^63到(2^63 - 1)，最后一位用于存储符号。在你的例子中，当计算大数字的乘法时，你的结果将溢出，64位数字(存储符号)将得到值1(这意味着-ve值)。

这就是你得到负值作为输出的原因。

Read this

Answer 2

您的算术溢出了C实现中long long中可表示的值。

此外，你正在做一个挑战性的问题或家庭作业，这在Stack Overflow上已经讨论过无数次了，你可以通过搜索“1000000007”来看到。

Answer 3

你需要小心使用(d*d*i)%MOD;，因为多个不带模的操作是不正确的，会在中考虑精度和溢出的风险。要严格地说对，你需要写

 return ((d*d)%MOD * i)%MOD;

即使在这种情况下，我也假设i == i%MOD

编辑:我举个例子：

log2((MOD-1)x(MOD-1)x25) = log2(1000000006x1000000006x25) = 64.438

这意味着您将在计算过程中使用此输入溢出。