7093 : 뤼카의 정리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
매우 큰 n, k와 상대적으로 작은 소수 p가 주어졌을 때, 이항계수 C(n, k) mod p를 계산하는 프로그램을 작성하십시오.
n, k의 범위가 10^18에 달하므로 뤼카의 정리(Lucas' Theorem)를 활용하십시오.
[제약 조건]
• $n, k$: $0 \le k \le n \le 10^{18}$, 소수 $p \le 100{,}000$
n, k의 범위가 10^18에 달하므로 뤼카의 정리(Lucas' Theorem)를 활용하십시오.
[제약 조건]
• $n, k$: $0 \le k \le n \le 10^{18}$, 소수 $p \le 100{,}000$
입력 설명
첫째 줄에 $n, k, p$가 공백으로 구분되어 주어집니다. ($0 \le k \le n \le 10^{18}$, $p$는 소수, $p \le 10^5$)
출력 설명
$\binom{n}{k} \bmod p$를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
뤼카의 정리를 사용하여 n과 k를 p진법으로 분해한 뒤,
C(n, k) ≡ ∏ C(n_i, k_i) (mod p)를 구현합니다.