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

Question

如果我有 2 intorlong long变量，调用它们aand b，并且我想计算 sum (a + b) mod p，其中 p 是一个大素数整数，我如何利用 C++ 中的模运算符来获得所需的结果？

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

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

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

标签： c++c++11summodulusinteger-overflow

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，因此我们可以安全地执行减法。

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