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

Question

如果我有 2 个int或long long变量，调用它们aand b，并且我想计算 sum (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=pa，所以 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，所以我们可以有把握地执行减法。

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