BOJ 3904 - The Teacher's Side of Math (Python3)

요즘 수학에 관심이 있고 잘 하는 사람 몇 명이 solved.ac 디스코드에 모여서 같이 어려운 수학 문제를 썰고 있다. 나도 나름 수학을 잘 한다고 생각하지만, 당연히 세상은 넓다. 이제 자부심은 떼야 할 것 같다.

그 디스코드 채널에서 나온 이야기다. 언제나처럼 두 명이서 수학 문제 관련된 이야기를 하고 있었는데, 조금 끔찍한 생각이 떠올라서 말을 꺼냈다. 그러고 나서 구현할 시간과 자신이 없어서 잠시 접어 뒀다가, 한 번 더 이야기를 꺼내고 구현을 시작했다. 아무리 봐도 답이 안 나와서 내가 망하고 있을 때 다른 분이 구현 된다고 검증하고 나서 디스코드에서 핑을 찍었다. 정작 나는 오타나 구현 오류 잡는다고 그 핑을 못 봤다. 1시간 정도 지나서 결정적인 오타 하나를 잡아낸 것 같다.

누구에게서 문제 아이디어를 듣는다는 정도의 참고도 없이 온전히 100% 나 혼자만의 힘으로 풀어낸 다이아 중위권 문제는 좀 오랜만이다(존재성을 알게 된 것 정도는 노 카운트로 치자.). 이 풀이방법을 시도해 본 사람은 두 사람밖에 없지 않을까? 나와, 검증해 주신 그 분을 제외하면. 애초에 이 풀이는 루비급 사전지식을 다이아에 박아넣는 정상이 아닌 풀이다. 모르는 사람은 시도조차 못 해봤을 것이다.

 

그럼 본격적으로 풀이에 돌입해 보자. 원문은 수록하지 않는다. 타이핑이 귀찮다.

---

문제

학생들이 수학 시간에 매일같이 하게 되는 작업 중 하나가 다항 방정식의 근을 구하는 것이다. 예를 들어서, \(X^2-4X+1=0\)이라는 방정식이 주어졌을 때 그것의 근 \(X=2\pm\sqrt{3}\)을 구하는 것과 같이 말이다.

학생들이 하는 작업이 주어진 다항 방정식의 근을 찾는 것이라면, 교사가 하는 작업은 주어진 근을 가진 다항식을 찾는 것이다. Galsone 선생은 열정적인 교사이지만, \(a+b\sqrt{c}\) 같은 근을 가지는 이차 방정식을 푸는 것에 질려 버리고 말았다. 그녀는 근이 살짝 더 복잡하고, 차수가 더 높은 방정식을 만들기를 원했다. 수학 시간에 보게 되는 문제들이 늘 그렇듯이, 그녀는 모든 계수가 정수이기를 원하고, 그에 더해 다항식의 차수가 최소가 되기를 원한다. 교사가 하는 작업을 수행하는 프로그램을 작성하여, 그녀를 도와 주자.

당신에게 \(t=\sqrt[m]{a}+\sqrt[n]{b}\) 꼴의 숫자가 주어진다. \(a, b\)는 서로 다른 소수이며, \(n, m\)은 1보다 큰 정수이다.

이 문제에서, 당신은 \(t\)를 근으로 가지는 최소다항식 \(F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0\)을 구해야 한다. 최소다항식은 다음 네 가지 조건을 충족해야 한다.

1. 계수 \(a_0, a_1, \cdots, a_d\)는 모두 정수여야 하고, \(a_d>0\)이어야 한다.

2. \(F(t)=0\)이어야 한다.

3. 다항식의 차수 \(d\)는, 위 두 조건을 만족하는 다항식들의 차수 중 가장 작아야 한다.

4. \(F(X)\)는 원시 다항식이어야 한다. 정확하게 말하자면, 계수들의 최대공약수 \(\text{gcd}(a_0, a_1, \cdots, a_d)\)는 정확하게 1이어야 한다.

예를 들어, \(\sqrt{2}+\sqrt{3}\)의 최소 다항식은 \(F(X)=X^4-10X^2+1\)이어야 한다. \(F(t)=0\)임을 검증하는 것은 아래에 서술되어 있듯, 굉장히 간단하다. (\(\alpha=\sqrt3, \beta=\sqrt2\)로 표기한다.)

\begin{align}F(t) &=(\alpha+\beta)^4-10(\alpha+\beta)^2+1\\&=(\alpha^4+4\alpha^3\beta+6\alpha^2\beta^2+4\alpha\beta^3+\beta^4)-10(\alpha^2+2\alpha\beta+\beta^2)+1\\&=(9+12\alpha\beta+36+8\alpha\beta+4)-10(3+2\alpha\beta+2)+1\\&=(9+36+4-50+1)+(12+8-20)\alpha\beta\\&=0\end{align}

실제로 \(F(X)\)의 차수가 최소인지 확인하는 것은 조금 더 어렵다. 다행히도 이 문제에서 주어진 조건, 즉 \(a, b\)가 서로 다른 소수이고 \(m, n\)이 1보다 크다는 조건에서 최소 다항식의 차수는 항상 \(mn\)이다. 게다가 최소 다항식의 최고차항 계수, 즉 \(a_d\)는 항상 1이다.

 

입력

입력은 \(t=\sqrt[m]{a}+\sqrt[n]{b}\)임을 의미하는 \(a\,m\,b\,n\) 형태의 여러 테스트케이스로 구성되어 있다. 한 줄에 네 개의 정수가 들어오고, 각 정수는 공백으로 구분되어 주어진다.

모든 테스트케이스는 \(\sqrt[n]{a}+\sqrt[m]{b}\le4\)이고, \(mn\le20\)이며, 또한 최소다항식의 계수 \(a_0, a_1, \cdots, a_d\)는 \(-2^{31}+1\) 이상 \(2^{31}-1\) 이하라는 조건을 만족한다.

입력의 마지막에는 \(0\,0\,0\,0\)과 같이, 네 개의 \(0\)이 공백으로 구분되어 주어진다.

 

예제 입력)

3 2 2 2
3 2 2 3
2 2 3 4
31 4 2 3
3 2 2 7
0 0 0 0

 

출력

각 테스트케이스에 대해, 한 줄에 하나씩 최소다항식 \(F(X)=a_dX^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0\)의 계수를 나타내는 \(d+1\)개의 정수를, \(a_d\,a_{d-1}\,\cdots\,a_1\,a_0\)과 같은 형식으로 출력하라.

음이 아닌 정수는 \(+,-\)와 같은 부호 없이 출력되어야 한다. 또한, 정수는 반드시 공백 하나로 구분되어야 하며 이외의 문자나 추가적인 공백은 출력하여서는 안 된다.

 

예제 출력)

1 0 -10 0 1
1 0 -9 -4 27 -36 -23
1 0 -8 0 18 0 -104 0 1
1 0 0 -8 -93 0 24 -2976 2883 -32 -3720 -23064 -29775
1 0 -21 0 189 0 -945 -4 2835 -252 -5103 -1260 5103 -756 -2183

 

---

내 코드

코드를 첨부하지 않는다. 부정행위를 방지하는 것도 없지는 않은데, 최소한 이 풀이가 정풀 같지는 않기 때문이라는 이유가 더 크다. 사전지식의 난이도로도 현재 이 문제의 난이도로 책정된 Diamond III는 뛰어넘고도 남는다. 여기에 사용된 사전지식인 종결식(resultant)은 대수학 쪽의 사전지식이고, 이 사전지식은 어지간해서는 학부 과정에서 다루어지지 않는다. 대학원 수준의 대수학 교과서인 S.Lang의 Algebra 정도는 되어야 등장하는 식이다.

물론 PS에는 쓰인다. 내가 이 resultant를 가져 오기로 결심한 이유는 이미 resultant를 사용한 문제 두 개를 풀어 본 적이 있었기 때문이고, 그 두 문제는 다음과 같다.

BOJ 18542 Permutant (Ruby III), BOJ 29257 하늘의 타일링 (Ruby II)

물론 이 두 문제가 resultant만 알고 있다고 풀리는 문제는 아니다. 하지만 이 이하의 문제에서 resultant를 사용하는 문제를 아직까지 본 적이 없고, 이와 동급으로 유명하지 않은 Lindstrom-Gessel-Viennot Lemma는 기초 문제가 이미 Diamond I이다. 아마 resultant 하나만으로도 그 정도 레벨은 갈 것 같다.

잡설이 길었다. 본문으로 들어가자.

 

복소수 범위에서 최소다항식은 항상 인수분해가 되고, 정수 범위에서는 더 이상 인수분해가 불가능할 것이며, 중근을 갖지 않을 것이라는 것은 예상해봄직하고, 실제로 사실이다. 현대대수 지식을 들고 온다면 이게 사실임을 증명할 수 있다. 여기서는 그냥 모든 root의 multiplicity가 같다를 사실로 간주하고, 그렇다면 \(t\)가 \(F(X)=0\)의 중근일 텐데 그렇다면 \(t\)가 \(\gcd(F(X), F'(X))\)의 근이라는 것 정도만 생각하면 된다. 더 이상 \(F\)이 최소다항식이 될 수 없어진다.

여기서 또 이 사실을 증명하지 않겠지만, 그리고 현대대수 지식을 또 들고 온다면 증명이 되겠지만, \(\zeta=\exp(\frac{2\pi i}{m}), \xi=\exp(\frac{2\pi i}{n})\)을 도입하면 최소다항식의 모든 근은 \(\sqrt[m]{a}\zeta^r+\sqrt[n]{b}\xi^s\,(0\le r<m, 0\le s<n)\) 꼴이다. 이는 임의의 \(r, s\)에 대해서 \(\sigma:(\sqrt[m]{a},\sqrt[n]{b})\mapsto(\sqrt[m]{a}\zeta^r,\sqrt[n]{b}\xi^s)\)이 \(\text{Gal}(\mathbb{Q}(\sqrt[n]{a},\sqrt[m]{b},\zeta,\xi)/\mathbb{Q})\)의 원소이기 때문이라고 생각하면 된다. \(\mathbb{Q}\)를 fix하기 때문에 \(0=\sigma (F(t))=F^\sigma(\sigma(t))=F(\sigma(t))\)이 성립하고, 이러한 \(\sigma\)가 딱 \(mn\)개 있으며 \(F\)는 중근을 가지지 않는 \(mn\)차 다항식이고 최고차항의 계수가 \(1\)이다.

지금까지의, 현대대수 시험장에서 이런 식으로 썼다면 점수의 절반도 못 가져 갈 논의과정을 종합하면 다음과 같은 결과를 얻을 수 있다.

\[F(X)=\prod_{s=0}^{n-1}\prod_{r=0}^{m-1}(X-(\sqrt[m]{a}\zeta^r+\sqrt[n]{b}\xi^s))\]

 

Resultant는 이제 등장할 차례이다. \(f(x)=A\prod_1^n(x-\alpha_i), g(x)=B\prod_1^m(x-\beta_i)\)로 인수분해된 두 다항식이 있을 때, 이 두 다항식의 resultant는 대응하는 Sylvester matrix의 행렬식이고, 구체적인 값은 다음과 같다.

\[\text{res}(f,g)=A^mB^n\prod_{r=1}^{n}\prod_{s=1}^m(\alpha_r-\beta_s)\]

이거 어디서 많이 본 꼴 아닌가? 그렇다. 바로 위 식과 같다. \(F(X)\)는 근이 \(X-\sqrt[m]{a}\zeta^r\)인 다항식 \(p\)와 근이 \(\sqrt[n]{b}\xi^s\)인 다항식 \(q\)의 resultant이다! 그리고 \(p, q\)를 찾기도, 게다가 직접 구성하기도 그렇게 어렵지 않다. \(p(x)=(X-x)^m-a, q(x)=x^n-b\)이다.

문제는 이 resultant라는 요상한 것을 어떻게 계산하느냐이다. 차수가 굉장히 작아서 계수 구하기가 매우 쉬우니 Sylvester 행렬을 직접 구해서 행렬식을 구해 보는 방안도 있다. AC를 받고 나서야 생각해 낸 방법이다. 왜 그 생각을 못 했지? 아무튼.

이 resultant라는 것은, \(f\)의 최고차항의 계수가 1이라면 사용할 수 있는 기막힌 성질이 하나 있다. 임의의 다항식 \(h\)에 대해서 \(\text{res}(f,g)=\text{res}(f,g-hf)\)라는 것이다. 이걸 이용해서 유클리드 호제법 식으로 차수를 줄일 수 있다. 다항식을 계수로 가지는 다항식에 대해서 이 짓을 할 수 있다면, 별도의 추가적인 조작 없이도 resultant를 통해 최소다항식을 한 방에 구할 수 있다.

 

그렇게 할 수 없다면, 예를 들어서 나처럼 마지막에 \(X^2+1, 2Xx\)같이 남았을 때 어째야 좋을까가 굉장히 고민된다면, 다항식 보간법을 사용하는 방법이 있다. 계수의 절댓값이 \(2^{31}\)을 넘지 않으므로, 적당히 큰 소수 \(p\)를 들고 오면(나는 \(p=10^{11}+3\)을 사용했다.) 모듈로 곱셈 역원을 이용한 나눗셈도 사용할 수 있다, \(mn+1\)개의 함숫값은 함수를 유일하게 결정하므로 \(X\)에 \(mn+1\)개의 값을 대입한 다음 resultant를 \(mn+1\)번 사용한 뒤 라그랑주 보간법을 이용하면 최소다항식을 복원할 수 있다. Resultant의 계산에는 \(mn\)이 매우 작은 관계로 상수로 취급해도 될 정도의 시간밖에 쓰이지 않는다.

어쨌든, 이걸 사용하면 어렵지 않게 AC를 얻을 수 있다.

 

이로서 3904번의 풀이를 마친다.