[BOJ] 17466번: N! mod P(1)

출처 : https://www.acmicpc.net/problem/17466

17466번: N! mod P (1)

 

 

 

1. 문제 설명 

양의 정수 N과, N보다 큰 소수 P가 주어질 때, N!을 P로 나눈 나머지를 구하여라.

 

 

2. 접근 방식 

모듈러 연산 특징을 활용하여 풀었다. 

 

A+B%C = ((A%C) + (B%C)) % C

A-B%C = ((A%C) - (B%C)) % C

A*B%C = ((A%C) * (B%C)) % C

 

언제 공부했더라.. 무튼 기억이 났다 ㅎ......

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
input = sys.stdin.readline
n, p = map(int, input().split())
total = 1
for i in range(2, n+1):
    total = (total * i) % p


print(total % p)

 

4. 분석 및 시간복잡도 

1 <= n, p < 10^8

python3은 시초가 떴다. 아무리 n번돌면서 상수 시간의 계산을 한다하더라도 10^8이라 상수시간도 무시못하는 듯하다. pypy로 돌려주자.