0
我想计算(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);
}
请帮我在此代码中发现的错误。
你真的需要'mulmod'吗?当'M'高达10^7时,'((N%M)*(N%M))%M *((N + 1)%M)'不会溢出。 – justanothercoder 2015-02-07 04:06:40
@justanothercoder divis by 2怎么样? – user3840069 2015-02-07 04:08:54
@justanothercoder您正在寻找N * N *(N + 1)。对 ? – user3840069 2015-02-07 04:12:06