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

Question

如果我有2个 int 或 long long 变量，称它们为 a 和 b而我想计算的是 (a + b) mod p其中p是一个大的质数，我如何利用C++中的modulo运算符来达到预期的结果？

我已经尝试过 (a + b) % p但这有时会产生溢出，因为 a + b 会在应用修改之前溢出。

我试过的其他类似方法似乎都能避免溢出，但结果却不正确。

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

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

EDIT: 诀窍是避免任何可能导致溢出的计算。而不知道极限在哪里。 我们只知道给定的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，那么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所以我们可以放心地进行减法。

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

Answer 2

有一个分配规则，但你必须应用修饰运算符最后一次。你看 本回答 的数学。

所以 (a + b) % p 成为 ( (a % p) + (b % p) ) % p.