| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 78 | 15 | 11 | 15.942% |
MatKor Cup에 모듈로 곱셈 역원이 자주 등장하는 이유를 아는가? MatKor는 사실 모든 물리량이$\bmod M$으로 표현되는 세계에 살고 있기 때문이다.
화학을 좋아하는 동우는 MatKor에서 화학 평형에 대한 강의를 하기로 했다. 동우는 강의를 하던 중 반응 지수가 무엇인지 설명했다. 반응 지수는 화학 평형에서 평형 상수와의 비교를 통해 반응의 진행 방향을 알아내는 데 사용된다.
$N$개의 기체 반응물 $A_1,ドル $A_2,ドル $\cdots,ドル $A_N$이 반응하여 $K$개의 기체 생성물 $B_1,ドル $B_2,ドル $\cdots,ドル $B_K$을 만드는 반응식 $a_1A_1+a_2A_2+\cdots +a_NA_N\rightleftharpoons b_1B_1+b_2B_2+\cdots +b_KB_K$에 대하여 반응 지수 $Q$는 다음과 같이 정의된다.
\[Q=\frac{\prod_{i=1}^K\left[ B_i \right]^{b_i}}{\prod_{i=1}^N\left[ A_i \right]^{a_i}} =\frac{\left[ B_1 \right]^{b_1}\left[ B_2 \right]^{b_2}\cdots\left[ B_K \right]^{b_K}}{\left[ A_1 \right]^{a_1}\left[ A_2 \right]^{a_2}\cdots\left[ A_N \right]^{a_N}}\]
여기서 $\left[ X \right]$은 물질 $X$의 농도를 의미한다.
예를 들어 중학교 과정에서 배우는 암모니아 합성 식 $N_2+3H_2\rightleftharpoons 2NH_3$의 경우 모두 기체일 때 반응 지수 $Q=\dfrac{\left[ NH_3 \right]^{2}}{\left[ N_2 \right]\left[ H_2 \right]^{3}}$이다.
이제 동우는 강의를 들은 재우가 잘 이해했는지 다음과 같이 테스트를 진행한다.
MatKor에서 수업했기 때문에 $i$번째 질문에 대한 대답을 $Q_i\pmod M$으로 해준다.재우는 이 테스트를 듣더니 만약 계수가 $Z$ 이상인 값이 존재한다면 반응식의 계수를 유일하게 결정하지 못할 수 있다고 하였다. 동우는 웃으며 모든 계수는 $Z$ 미만임이 보장된다고 말하였다. 즉, $Z$ 미만의 계수에서는 반응식의 계수가 무엇이든지 반응식을 유일하게 결정할 수 있는 반응식이 존재함이 보장되며, 계수가 $Z$ 이상인 값이 존재하면 유일하게 결정하지 못하는 경우가 생긴다.
재우를 도와 동우의 테스트를 통과해 보자.
유리수의 나머지는 다음과 같이 정의된다. 기약 분수 $\frac{p}{q}(p\ge 0,q>0,\gcd(p,q) =1)$를 $M$으로 나눈 나머지는 $q^{-1}$가 $q\cdot q^{-1}\equiv 1\pmod M$을 만족하는 정수, 즉 $q$의 $M$에 대한 모듈로 곱셈 역원일 때, $p\cdot q^{-1}\pmod M$로 정의한다. 만약 정수일 경우 $q=q^{-1}=1$이므로 $p\pmod M$를 의미한다.
농도가 $M$과 서로소라면, 분모의 $M$에 대한 모듈로 곱셈 역원이 존재하므로 반응 지수에 대한 $Q\pmod M$을 구할 수 있다.
컴퓨터는 동우, 유저는 재우로 생각하고 인터랙티브가 진행된다. 인터랙티브는 다음과 같이 컴퓨터와 유저가 3ドル$번씩 상호작용한다.
먼저 컴퓨터가 모듈로를 나타내는 정수 $M(2\le M\le 10^9)$을 입력으로 준다.
입력을 받은 후 조건을 만족하는 최소의 정수 $Z$를 출력한다. 만약 $Z$가 잘못되었다면 컴퓨터는 틀렸습니다를 띄우고 프로그램을 종료한다.
다음으로 컴퓨터가 반응물의 개수를 나타내는 정수 $N=200$과 생성물의 개수를 나타내는 정수 $K=200$를 입력으로 준다.
유저는 $N+K$개의 줄에 걸쳐 각 줄에 반응물과 생성물의 농도를 나타내는 질문을 출력한다. 각 줄은 $N+K$개의 정수를 출력해야 하며, 앞의 $N$개의 정수는 순서대로 $\left[ A_1 \right],ドル $\left[ A_2 \right],ドル $\cdots,ドル $\left[ A_N \right]$을, 다음 $K$개의 정수는 순서대로 $\left[ B_1 \right],ドル $\left[ B_2 \right],ドル $\cdots,ドル $\left[ B_K \right]$을 출력한다. 모든 농도는 $M$과 서로소인 1ドル$이상 $M$ 이하의 정수여야 한다. 조건을 만족하지 않는다면, 컴퓨터는 틀렸습니다를 띄우고 프로그램을 종료한다.
다음으로 컴퓨터가 한 줄에 $N+K$개의 정수를 준다. $i$번째 정수는 $i$번째 질문에 대한 반응 지수 $Q_i\pmod M$를 의미한다.
유저는 반응식의 계수를 의미하는 $N+K$개의 정수를 한 줄에 출력한다. 앞의 $N$개의 정수는 $a_1,ドル $a_2,ドル $\cdots,ドル $a_N$을, 다음 $K$개의 정수는 $b_1,ドル $b_2,ドル $\cdots,ドル $b_K$를 의미한다. 모든 계수는 1ドル$ 이상 $Z$미만이여야 한다. 조건을 만족하지 않거나 잘못된 답을 출력하는 경우, 컴퓨터는 틀렸습니다를 띄우고 프로그램을 종료한다.
유저는 출력 후 다른 출력 없이 프로그램을 종료해야 한다.
인터랙션 도중 컴퓨터에게 정상적인 출력이 전달되지 않았거나 덜 전달된 경우, flush를 하지 않은 경우, 혹은 정답 출력 후 프로그램이 종료되지 않는 경우 등의 상황에는 시간 초과를 받을 수 있다.
반응식의 모든 계수는 1ドル$이상 $Z$미만의 정수임이 보장된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 9 | $M=25$ |
| 2 | 9 | $M=30$ |
| 3 | 37 | $M$은 10ドル^9$ 이하의 소수 |
| 4 | 45 | 추가적인 제한 조건 없음 |
3 2 2 1 1 1 2
3 1 2 1 2 2 2 2 2 1 2 1 1 2 1 1 2 1 2 1 2
이 예제는 $A_1+2A_2\rightleftharpoons B_1+2B_2$의 반응 식에 대한 예제이다. 이 경우 반응 지수 $Q=\frac{\left[ B_1 \right]\left[ B_2 \right]^{2}}{\left[ A_1 \right]\left[ A_2 \right]^{2}}$이다.
실제로 이러한 예시로 매우 높은 온도에서 진행되는 메테인($\rm CH_4$) 연소 반응인 ${\rm C}{{\rm H}_4}\left( g \right) +2{{\rm O}_2}\left( g \right)\rightleftharpoons{\rm C}{{\rm O}_2}\left( g \right) +2{{\rm H}_2}{\rm O}\left( g \right)$ 등이 있다.
먼저 컴퓨터가 모듈로를 나타내는 정수 3ドル$을 준다.
유저는 이를 입력받아 조건을 만족하는 최소의 정수 $Z$인 3ドル$을 출력하였다.
이어 컴퓨터는 $N=K=2$를 입력으로 준다. 이는 예제를 위한 데이터로, 실제 채점되는 데이터에서는 $N=K=200$인 데이터만 주어진다.
유저는 농도에 해당하는 4ドル\times 4$개의 정수를 출력하였다.
컴퓨터는 각 줄에 대한 반응 지수를 계산해 준다. 구체적으로 다음과 같다.
$Q_1=\frac{1^1\cdot 2^2}{1^1\cdot 2^2} =1,ドル $Q_2=\frac{2^1\cdot 2^2}{2^1\cdot 2^2} =1,ドル $Q_3=\frac{1^1\cdot 1^2}{1^1\cdot 2^2} =1,ドル $Q_4=\frac{1^1\cdot 2^2}{2^1\cdot 1^2} =2$
유저는 이를 받고 유추하여 계수를 출력한다.
입출력이 분모, 분자의 순서로 진행됨에 유의하자.
21 5 5 19 13 4 16 8 13 4 11 4 1
7 1 2 4 5 8 10 11 13 16 17 19 20 20 19 17 16 13 11 10 10 5 4 2 1 8 20 20 16 13 16 4 8 19 17 10 11 13 17 17 4 10 5 16 13 10 8 20 16 4 1 11 13 16 8 20 16 17 8 2 1 20 16 17 20 1 1 1 2 4 1 2 2 2 2 2 2 2 2 2 2 4 4 4 4 4 5 5 5 5 5 20 19 17 16 13 11 17 10 8 5 1 3 5 2 4 6 4 2 5 3
이는 예제를 위한 데이터로, 실제 채점되는 데이터에서는 $N=K=200$인 데이터만 주어진다.
University > 고려대학교 > MatKor Cup > 제5회 고려대학교 MatKor Cup: 2024 Summer/Fall N번