c - 为什么我得到一个负值？

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 longC 实现中可表示的值。

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

Answer 2

signed long long 的范围是 -2^63 到 (2^63 - 1)，最后一位用于存储 sign 。在您的情况下，当计算大数的乘法时，您的结果将溢出并且数字的第 64 位（存储符号）将获得值 1（这意味着 -ve 值）。

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

读这个

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

这意味着您将在计算期间使用此输入溢出。