Wednesday 15 January 2014

Multiplication of two long numbers modulo a long number.

LL multiplication (LL a, LL b, LL mod) {
    LL res = (a * ((long double) b / (long double) mod));
    // put the number in long double, and then reduce the value to LL, forget 
    overflow.
    res = a * b - res * mod;
    if (res >= mod) res -= mod;
    if (res < 0) res += mod;
    return res;
}

No comments:

Post a Comment