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

Question

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

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

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

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

Answer 1

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 . (声明的类型是无符号的，但我们也可以避免使用负数，如果只是因为它们的限制有时与正限制的负值相差一个，以我永远不记得的方式。)

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

如果b<c , 然后 a+b<p , 所以我们可以安全地计算 a+b (并且不需要应用模数​​)。

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

(*) _{没错，我说的是“不敢”。这是一个非常好的词。}