"compute 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

기본 아이디어는 곱셈의 전, 중 또는 후에 모듈러스를 취할 수 있고 최종 결과의 모듈러스를 취한 후에 같은 값을 얻을 수 있다는 것입니다.

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

@ 피터가 지적 하듯이, 계승을 위해

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

는, 그래서 우리는

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

는 각 반복 후 계수를 가지고 있습니다.

---

이 방법으로 그 일을의 장점은 사용자의 수를 폭파하고 중간 계수의 값을 고려하지 않은 경우가 꽤 빨리 할 것처럼 오래 오래 유형을 오버플로되지 것입니다.