对 1e9 + 7 取模

Posted on 2022-11-19 In 算法 Views: Disqus: Reading time ≈ 1 mins.

为什么取模

OJ 上很多题目因为难度原因需要非常大的测试数据量（数据量大了自然会对算法的时间复杂度要求更高），而大数据量往往会导致溢出，虽然可以用 BigInt 等方式做题，但这就失去了这道题的原本意义。

这种情况题目会要求计算结果对 1e9 + 7 取模，因为对取模不会影响算法的正确性，既避免了高精度运算，又能保证极少的冲突情况。
这里可以先回顾下模除运算的等价性

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

由上述各个公式可知只要每次运算后觉得结果过大都可以对其进行取模，只要避免数据溢出，那么最终结果都是一样的。例如：

int MOD = (int) 1e9 + 7;

int a = MOD + 1;
int sum = a + 1 + a * a;
sum %= MOD;

只要 sum 不溢出，那么其结果和对每次运算结果都 %MOD 一遍是一样的。

所以 取模成了简化大数据的一种约定，服务端给定算法取模后的测试数据，我们写算法时也进行取模，那么依然能验证算法的正确性。