c++ - 有没有办法对 unsigned long long A 和 B 进行 (A*B) mod M 而不会溢出？

Question

我不想在 Windows 上安装 GMP 的噩梦。

我有两个数字 A 和 B，unsigned long long，数量级最多为 10^10 左右，但即使在执行 ((A%M)* (B%M))%M，我得到了整数溢出。

是否有用于计算更大数字的 (A*B)%M 的自制函数？

Answer 1

如果模数M比 ULLONG_MAX 足够小(如果它在 10^10 范围内就是这种情况)，您可以通过将其中一个因素分成两部分来分三步完成。我假设 A < M和 B < M , 和 M < 2^42 .

// split A into to parts
unsigned long long a1 = (A >> 21), a2 = A & ((1ull << 21) - 1);
unsigned long long temp = (a1 * B) % M;   // doesn't overflow under the assumptions
temp = (temp << 21) % M;                  // this neither
temp += (a2*B) % M;                       // nor this
return temp % M;

对于较大的值，您可以将因子分成三部分，但如果模数变得非常接近 ULLONG_MAX它变得丑陋。