| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 0.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 40 | 17 | 14 | 70.000% |
NP-Hard와 NP-Complete가 무엇인지 아는가?
익명을 요구한 MatKor 출제/검수진 누군가는 다음과 같이 대답했다.
양의 정수 $N$과 소수 $P$가 주어질 때, $\binom{N}{i}\equiv 0\pmod P$를 만족하는 0ドル$ 이상 $N$ 이하의 정수 $i$의 개수를 구하는 문제는 너무 쉽게 풀리므로, NP-Complete이다. 이제 음이 아닌 정수 $K$를 하나 더 입력으로 주어, $\binom{N}{i}\equiv 0\pmod{P^K}$를 만족하는 0ドル$이상 $N$이하의 정수 $i$의 개수를 구해보자.
첫 번째 줄에 테스트 케이스의 개수 $T(1\le T\le 1,円 000)$이 주어진다.
두 번째 줄부터 $T$ 줄에 걸쳐 양의 정수 $N(1\le N\le 10^{18})$과 소수 $P(2\le P\le 10^{18}),ドル 정수 $K(0\le K\le 10^{18})$이 공백으로 구분되어 주어진다.
첫 번째 줄부터 $T$ 줄에 걸쳐 각 테스트 케이스 별로 문제의 정답을 한 줄에 한 개씩 출력한다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 6 | $K=0$ |
| 2 | 16 | $P=2$; $K\le 1$ |
| 3 | 30 | $P=2$ |
| 4 | 21 | $K\le 1$ |
| 5 | 27 | 추가적인 제한 조건 없음 |
11 4 2 0 4 2 1 4 2 2 25 3 1 26 3 1 27 3 1 25 3 2 26 3 2 27 3 2 27 3 3 27 3 4
5 3 2 8 0 26 2 0 24 18 0
테스트 케이스 1ドル$부터 3ドル$에서 $\binom{4}{i}$는 $i=0,1,2,3,4$일 때 순서대로 1,4,6,4,1ドル$이므로, 2ドル^0,2^1,2^2$의 배수는 각각 5,3,2ドル$개다.
테스트 케이스 7ドル$에서 $\binom{25}{i}$중 3ドル^2$의 배수는 $\binom{25}{8} =\binom{25}{17} =1,円 081,円 575$로 2ドル$개다.
University > 고려대학교 > MatKor Cup > 제7회 고려대학교 MatKor Cup: 2025 Summer, The FinAL D번