pascal 31738번 매우 어려운 문제 (백준)

var n,m,i,a:int64;
begin
a:=1;
readln(n,m);
if n<m then begin for i:=2 to n do a := (a*i) mod m end
else a:=0;
write(a);
end.

 

풀이 : 모듈러 연산

 

모듈러 연산은 (산술) 분배법칙이 성립합니다.

 

(A*B*C)%M ->

( (A%M)*(B%M)*(C%M) ) % M

 

이런식으로 성립합니다.

 

그러나 범위가 크기 때문에 10^18까지 하기엔 무리가 있습니다.

그렇지만 n >= m 인 경우 n!에는 m이 존재하므로 m 은 n!의 약수임을 알 수 있으며 이는 (n>=m) n! % m = 0 이란 의미입니다.

 

문제에서 주어진 2<=M<=10^7 정도 되기 때문에

(10^7-1)! 까지는 반복적으로 나머지 연산을 해도 시간안에 처리가 가능합니다.