How can I calculate (A*B)%C for A,B,C <= 10^18, in C++?

Question

For example, A=10^17, B=10^17, C=10^18.
The product A*B exceeds the limit of long long int.
Also, writing ((A%C)*(B%C))%C doesn't help.

Answer 1

Assuming you want to stay within 64-bit integer operations, you can use binary long division, which boils down to a bunch of adds and multiply by two operations. This means you also need overflow-proof versions of those operators, but those are relatively simple.

Here is some Java code that assumes A and B are already positive and less than M. If not, it's easy to make them so beforehand.

// assumes a and b are already less than m
public static long addMod(long a, long b, long m) {
    if (a + b < 0)
        return (a - m) + b;  // avoid overflow
    else if (a + b >= m)
        return a + b - m;
    else
        return a + b;
}

// assumes a and b are already less than m
public static long multiplyMod(long a, long b, long m) {
    if (b == 0 || a <= Long.MAX_VALUE / b)
        return a * b % m;   // a*b > c if and only if a > c/b
    // a * b would overflow; binary long division:
    long result = 0;
    if (a > b) {
        long c = b;
        b = a;
        a = c;
    }
    while (a > 0) {
        if ((a & 1) != 0) {
            result = addMod(result, b, m);
        }
        a >>= 1;
        // compute b << 1 % m without overflow
        b -= m - b; // equivalent to b = 2 * b - m
        if (b < 0)
            b += m;
    }
    return result;
}

Answer 2

You can use

• The GNU Multiple Precision Arithmetic Library

  https://gmplib.org/

or

• C++ Big Integer Library

  https://mattmccutchen.net/bigint/

If you work only with power of 10 numbers, you could create a simple class with 2 members: a base and the power of 10, so A=10^17 would be {1, 17}. Implementing adding, subtracting, multiply and division is very easy and so is the print.