在 C++ 中避免整数溢出的模数函数

Question

如果我有 2 个 int 或 long long 变量，将它们命名为 a 和 b，我想计算总和 (a + b) mod p，其中p 是一个大质数整数，我如何利用 C++ 中的 modulo 运算符来获得所需的结果？

我试过 (a + b) % p，但这有时会导致溢出，因为 a + b 会在应用 mod 之前溢出。

我尝试过的其他类似方法似乎可以避免溢出，但给出的结果不正确。

在这种情况下如何使用 modulo 运算符来正确计算所需的总和，同时避免溢出？

Answer 1

有一个分配规则，但你必须最后一次应用mod运算符。请参阅 this answer 了解数学。

因此 (a + b) % p 变为 ( (a % p) + (b % p) ) % p。

Answer 2

a %= p
b %= p
c = p-a

if(b==c)
  sum = 0
if (b<c)
 sum = a+b
if (b>c)
 sum = b-c

编辑：诀窍是避免任何可能导致溢出的计算，不知道限制在哪里。我们所知道的是给定的 a、b 和 p 低于限制 - 可能只是低于限制。

经过前两步 (a%=p;b%=p;) 我们知道 a<p 和 b<p。我们还是不敢加a+b，因为那个和可能会超过p，突破极限^*。但是我们可以看到 c = p-a 还剩下多少空间，这是安全的，因为我们知道 c<=p 和 c>0。（声明的类型是无符号的，但我们也可以避免使用负数，因为它们的极限有时会与 positive 极限的负数相差一个，以我永远不记得的方式.)

如果b=c，则b=p-a，所以a+b=p，所以和(mod p)为零

如果b<c，则a+b<p，所以我们可以安全地计算a+b（并且不需要应用modulo）。

如果 b>c，那么计算 a+b 是不安全的，但我们知道我们要查找的数字是 a+b-p，我们可以将其重写为 b-(p-a)，并且我们已经有了 b 和 p-a，因此我们可以安全地执行该减法。

(*) _{没错，我说的是"daren't"。真是个好词。}

在 C++ 中避免整数溢出的模数函数

Modulus Function to Avoid Integer Overflow in C++

c++

c++11

sum

modulus

integer-overflow