Ronzii's Blog

Just your average geek's blog

Optimal computation of 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;
}

Read more at Topcoder

Advertisements

March 4, 2012 Posted by | C++ | , , , | Leave a comment