"compute n! under 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 类型，如果你不采用中间模值，它会很快。

Math behind "compute n! under modulo p"?