乘法时溢出

Question

我想计算 (N* N *(N+1)/2) mod M 的值，其中 N 可以达到 10^18，M 最大可以达到 10^7。我试图对其进行编码，但不知道它溢出的原因。这是我的代码：

主要是我做了这样的事情:

long long tt=mulmod(N,N+1,MOD)*InverseEuler(2,MOD);
long long mm=mulmod(tt,N,MOD);

和 mulmod 函数查找 (A*B)%C 。如下：

long long mulmod(long long a,long long b,long long c)
{    
    long long x = 0,y = a%c;
    while(b > 0)
    {
        if(b%2 == 1)
        {
            x = (x+y)%c;
        }
        y = (y*2)%c;
        b /= 2;
    }
    return x%c;
}

逆欧拉也是这样的:

long long p(long long n,int m,long long int MOD)
{
    if(m == 0) return 1%MOD;

    long long x = p(n,m/2,MOD);
    if(m%2 == 0)
        return (x*x)%MOD;
    else
        return (((x*x)%MOD)*n)%MOD;
}
long long InverseEuler(int n,int MOD)
{
    return p(n,MOD-2,MOD);
}

请帮我找出这段代码中的错误。

Answer 1

事实是，如果提供了正确（或错误）的操作数集，每个操作都会溢出。

justanothercode 在评论中暗示模 10^7 不会溢出 long long（事实上它不会溢出 long）

您需要利用

的身份

(a+b)%c == ((a%c) + (b%c))%c
(a*b)%c == ((a%c)*(b%c))%c

这些恒等式的数学证明很简单。

当 a 和 b 的值接近 long long 可以表示的极限时，将它们相加或相乘可能会溢出。但是，这些标识右侧的表达式使用模运算符来避免可能溢出的加法或乘法。

也不需要使用循环。

乘法时溢出

Overflow while doing multiplication

c++

integer-division

c++11