Hello,

I have AC now. I used code from here:
http://stackoverflow.com/a/21032389

Is there more clever way to value (a*b)%c?

long long mul(long long a,long long n)
{
     long long ret;
     if(n==0)
       return 0;
     ret=mul(a,n/2);
     ret=(ret+ret)%mod;
     if(n%2)
        ret=(ret+a)%mod;
     return ret;
}

Edited by author 24.11.2016 05:02

LL product_mod(LL a, LL b, LL mod)
{
    a %= mod;
    b %= mod;

    LL result = 0, y = a;

    while(b)
    {
        if(b&1)
            result = ((result%mod) + y) %mod;

        y = (y + y)%mod;

        b = b >> 1;
    }

    return result%mod;
}

This is also known as the Russian peasant method for multiplication.

For example, 7x13

13 = (8 + 4 + 1)

The product is re-written as 8.7 + 4.7. 1.7

In my code, y keeps track of 7, 2.7. 4.7, 8.7, etc.
It gets added to result whenever a bit is set in b.

long long c = (__int128_t)a*b%md;
he he)

Edited by author 14.05.2021 21:34

Edited by author 14.05.2021 21:34