数学背后“计算n！在modulo p“下？

Question

long long x;
for (int i = 1; i <= n; i++) {
    x = (x * i) % m;
}
cout << x;

这是计算（n！）mod m（假设m> n）的技巧。但是，我不知道为什么会这样。你能解释一下这背后的数学机制吗？

Answer 1

这里的基本思想是你可以在乘法之前，期间或之后取模数，并在取最终结果的模数后得到相同的值。

正如@Peter指出的那样，

(a * b) % m == ((a % m) * (b % m)) % m

对于阶乘，

n! = 1 * 2 * 3 * ... * (n-1) * n

所以我们有

n! % m = (((((((1 * 2) % m) * 3) % m) * ... * n-1) % m) * n) % m

每次迭代后取模数。

---

这样做的好处是，如果你没有采用中间模数值，那么你的数字就不会爆炸并溢出你的long long类型，就像它会很快就会这样。