Geek Answers Handbook

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

For example, A = 10 17, B = 10 17, C = 10 18.
Product A * B exceeds the limit of a long, long string.
In addition, writing ((A% C) * (B% C))% C does not help.

+4
source share
2 answers

Assuming you want to stay in 64-bit integer operations, you can use binary long division, which boils down to a bunch of additions and is multiplied by two operations. This means that you also need overflowing versions of these statements, but they are relatively simple.

Java-, , A B M. , .

// 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;
}
+1

10 , 2 : 10, A = 10 ^ 17 {1, 17}. , , , .

+2

More articles:


All Articles