Overflow while doing multiplication

Question

I want to calculate value of (N* N *(N+1)/2) mod M where this N can go upto 10^18 and M is at max up to 10^7. I tried to code it but don't know the reason that why it is overflowing. Here is my code :

In main I do something like this :

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

And mulmod function find (A*B)%C . It is as follow :

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

Also Inverse Euler is something like this :

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

Please help me in finding error in this code.

Answer 1

The thing is, every operation will overflow if the right (or wrong) set of operands are provided.

justanothercode has hinted in comments that modulo 10^7 will not overflow a long long (in fact it won't overflow a long)

You need to make use of the identities that

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

The mathematical proofs of these identities are trivial.

With values a and b near the limits of what a long long can represent, adding or multiplying them can overflow. However, the expression on the right of these identities use the modulo operator to avoid additions or multiplications that can overflow.

No need to use a loop either.