“计算n！"后面的数学运算！在模p"下? [英] Math behind "compute n! under modulo p"?

问题描述

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

这是计算(n！)mod m的技巧(假设m> n).但是，我不知道为什么这是真的.您能解释一下其背后的数学机制吗?

解决方案

此处的基本思想是，您可以在乘法之前，期间或之后获取模数，并在获取最终结果的模数后获得相同的值. /p>

@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类型，就像不使用中间模数值那样很快.

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

This is the trick to calculate (n!) mod m (assume m > n). However, I don't know why it's true. Can you explain the math mechanism behind this?

解决方案

The basic idea here is that you can take the modulus before, during, or after multiplication and get the same value after taking the modulus of the final result.

As @Peter points out,

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

For the factorial,

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

so we have

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

taking the modulus after each iteration.

---

The advantage to doing it this way is that your number won't blow up and overflow your long long type like it would do pretty quickly if you didn't take intermediate modulus values.

这篇关于“计算n！"后面的数学运算！在模p"下?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！