[BAEKJOON] 31738 매우 어려운 문제

문제

제목과 다르게 이 문제는 아주 쉽다.

2 이상의 정수 $N$, $M$에 대하여, $N!$을 $M$으로 나눈 나머지를 구하여라.

입력

첫 번째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 문제의 답에 해당하는 정수를 출력한다.

제한

•  $2 \leq N \leq 10^{18}$ ($N$ 제한에 주의하라)
•  $2 \leq M \leq 10^7$ 
•  $N$, $M$은 정수이다.

예제 입력 1 

5 7

예제 출력 1 

1

 $5!$을 계산하면 $5\times4\times3\times2\times1=120$이다. 따라서 이 값을 $7$로 나누면 $1$이 된다.

노트

•  $n!$은 $1$ 이상 $n$ 이하의 모든 정수의 곱을 의미하며 "$n$ 팩토리얼"이라고 읽는다. 즉, $n!=n\times(n-1)\times(n-2)\times\cdots\times2\times1$이다.
• 이 문제의 일부 테스트 케이스는 답의 범위가 $2^{31}$을 넘어갈 수 있으므로 long long 자료형을 쓰도록 하자.

---

이게 왜 실버5 문제지? 하고 바로 풀었다.

자꾸 문제 푸는데 시간 초과가 뜸 ㄱ-

 

글 읽기 - 해당문제 반례를 못찾겠습니다.

 

해당 질문 글의 답변이 도움이 많이 되었다.

 

n, m의 범위를 체크해서 최대한 케이스를 빨리 처리하고,

mod 함수의 성질 기억하기

 

n, m = map(int, input().split())

if n < m:
    t = 1
    for i in range(n, 1, -1):
        t *= i

    print(t % m)
else:
    print(0)

 

그래서 위의 코드가 시간 초과가 떳음

 

n, m = map(int, input().split())

if n < m:
    t = 1
    for i in range(n, 1, -1):
        t *= i
        t %= m

    print(t)
else:
    print(0)