문제
양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라.
입력
첫째 줄에 N과 P가 공백으로 구분되어 주어진다.
출력
N!을 P로 나눈 나머지를 구하여라.
제한
1 ≤ N < P ≤ 108
P는 소수
내 풀이
n, p = map(int, input().split())
answer = n
for i in range(n-1, 1, -1):
answer = answer*i%p
print(answer%p)코멘트
모듈러 연산을 이용하면 pypy3 한정으로 정답을 받을 수 있다. (python으로는 어떻게 풀어도 시간 초과를 받을 수 밖에 없는 듯)
모듈러 연산(modular arithmetic)은 어떤 수를 나눈 뒤 남는 나머지를 구하는 연산이다. 프로그래밍에서는 큰 수를 계산하면 오버플로우가 발생할 수 있으므로, 중간 계산마다 모듈러 연산을 적용해서 수를 제한한다. 모듈러 연산은 다음과 같은 성질이 있기 때문에, 중간 계산마다 모듈러 연산을 해도 최종 계산 결과에만 모듈러 연산을 한 것과 같아진다.
덧셈
(a + b) mod m = ((a mod m) + (b mod m)) mod m곱셈
(a x b) mod m = ((a mod m) x (b mod m)) mod m뺄셈
(a - b) mod m = ((a mod m) - (b mod m)) mod m