如何在C ++中计算A，B，C <= 10 ^ 18的（A * B）％C？ [英] How can I calculate (A*B)%C for A,B,C &lt;= 10^18, in C++?

问题描述

例如，A = 10 ^ 17，B = 10 ^ 17，C = 10 ^ 18。

产品A * B超过long long int的限制。

此外，写（（A％C）*（B％C））％C不帮助。

解决方案

假设您希望保留在64位整数运算中，可以使用二进制长除法，一堆添加和乘以两个操作。这意味着你还需要这些操作符的溢出防护版本，但是这些操作符相对简单。

这里是一些Java代码，假设A和B已经是正数，小于

  //假定a和b已经小于m 
 public static long addMod（long a，long b，long m）{
 if（a + b< 0）
 return（a-m）+ b; //避免溢出
 else if（a + b> = m）
 return a + b-m; 
 else 
 return a + b; 
} 
 
 //假设a和b已经小于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当且仅当a> c / b 
 // a * b会溢出;二进制长除法：
 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无溢出
 b  -  = m  -  b; //等价于b = 2 * b-m 
 if（b <0）
 b + = m; 
} 
 return result; 
} 
  

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.

解决方案

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;
}

这篇关于如何在C ++中计算A，B，C <= 10 ^ 18的（A * B）％C？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！