소수 거듭제곱으로 나눈 이항계수
다이아몬드 I의견: 0
소수 \(p\) 와 양의 정수 \(q\) 가 주어진다. 법은 \(M = p^{q}\) 이다.
이후 \(T\) 개의 질의가 주어지며, 각 질의는 두 정수 \(n\), \(k\) 로 이루어진다. 각 질의마다 이항계수 $$ \binom{n}{k} \bmod M $$ 을 구하여라. 단 \(0 \le k \le n\) 이며, \(k < 0\) 또는 \(k > n\) 인 경우는 주어지지 않는다.
\(n\), \(k\) 가 \(10^{18}\) 까지 커질 수 있으므로 이항계수를 직접 계산할 수 없다.
\(p\) 는 소수, \(1 \le q\), \(2 \le p^q \le 10^{6}\)
\(1 \le T \le 10^{4}\)
\(0 \le k \le n \le 10^{18}\)
첫 줄에 세 정수 \(p\), \(q\), \(T\) 가 주어진다 (\(M = p^q\)).
이어서 \(T\) 개의 줄에 각 질의의 두 정수 \(n\), \(k\) 가 주어진다.
각 질의마다 \(\dbinom{n}{k} \bmod p^q\) 의 값을 한 줄에 하나씩 출력한다.
3 2 3
5 2
6 3
10 4
1
2
3법 \(3^2=9\). \(\binom{5}{2}=10\equiv1\), \(\binom{6}{3}=20\equiv2\), \(\binom{10}{4}=210\equiv3 \pmod 9\).
2 3 2
1000000000000000000 2
4 2
0
6법 \(2^3=8\). \(\binom{4}{2}=6\). 큰 \(n=10^{18}\) 에 대해서도 직접 계산 없이 답을 구한다.
riseoj 작성
출처 Original
평가 및 의견
소수 거듭제곱으로 나눈 이항계수
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
소수 거듭제곱으로 나눈 이항계수