这是计算(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)) % mFor the factorial,
n! = 1 * 2 * 3 * ... * (n-1) * nso we have
n! % m = (((((((1 * 2) % m) * 3) % m) * ... * n-1) % m) * n) % mtaking 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"下?
发布评论