一些算法公式技巧摘录

本文摘录模运算中加法、减法和乘法的基本关系。

余法运算公式

a mod b 表示 a 对 b 取模。以下等式按数学模运算理解：a、b 为整数，模数 p 为正整数，% 的结果取 0 到 p−1 之间的非负余数。

• (a + b) % p = (a%p + b%p) %p
• (a - b) % p = ((a%p - b%p) + p) %p
• (a * b) % p = (a%p)*(b%p) %p

如果直接用 C/C++ 的 % 求余，减法式的两边可能不同：例如 a=0、b=1、p=2 时，左边为 -1，右边为 1。实现数学取模时需要统一处理负余数，并避免中间的加、减、乘法溢出。C 语言求余规则可参见 C11 公开草案 N1570 §6.5.5。