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?
Asked
Active
Viewed 632 times
0
buzzerbeater27
- 31
- 6
-
7This question should be moved to https://math.stackexchange.com/ – Julian Heinovski Dec 26 '17 at 23:46
-
@hvd well than it should be closed ;-) – Julian Heinovski Dec 26 '17 at 23:48
-
No. In this case m should be larger than n. – buzzerbeater27 Dec 26 '17 at 23:50
-
@JulianHeinovski Actually looking more closely it wouldn't be a duplicate of that. I'm sure it's been asked before though, let me see if I can find a better link. – Dec 26 '17 at 23:50
-
Not exactly a duplicate, but https://math.stackexchange.com/questions/346271/rules-for-algebra-equations-involving-modulo-operations/346277 does hint at why this works. – Dec 26 '17 at 23:57
-
2There is no trick here, it's all straightforward. Which part do you think involves a trick? – President James K. Polk Dec 27 '17 at 00:01
-
1If you want a short answer, there's a proof for it, which I'm pretty sure you can find it if you type "modular arithmetic properties" on google – Francisco Gallego Salido Dec 27 '17 at 00:04
-
Basic (and easily provable) property of modulo arithmetic. `(a * b) % m == ((a % m) * (b % m)) % m` (non-zero `m`). – Peter Dec 27 '17 at 01:25
-
it's just simply [modulo math](https://stackoverflow.com/q/2177781/995714), just like how you do [modular exponentiation](https://stackoverflow.com/q/8496182/995714) – phuclv Dec 27 '17 at 01:50
1 Answers
2
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.
Alexis Olson
- 38,724
- 7
- 42
- 64