[백준 3904] The Teacher's Side of Math (Diamond IV)

https://www.acmicpc.net/problem/3904

3904번: The Teacher's Side of Math

 

 $\sqrt[m]{a}+\sqrt[n]{b}$를 근으로 갖는 정수 계수 mn차 다항식을 찾는 문제다. gaussian elimination을 전혀 사용하지 않는 풀이를 소개한다.

 

 일단 b = 0일 때 $\sqrt[m]{a}$를 근으로 갖는 정수 계수 m차 다항식이 $x^m-a$라는 사실은 너무나 쉽게 찾아줄 수 있다. a = 0일 때도 똑같이 해 줄 수 있다. $f=x^m-a,g=x^n-b$라 놓고, 두 방정식의 영점 집합을 각각 $A,B$라 하자. 이제 다음 집합

 

$$A+B=\{x+y:x\in A,y\in B\}$$

 

 의 모든 원소를 영점으로 갖는 정수 계수 다항식이 정답이 된다. 이러한 다항식이 정수 계수일 것이라고 감을 잡는 것은 쉽지만 엄밀한 증명은 어려운데, 어차피 찾는 과정에서 다 증명이 되므로 일단은 대충 넘어가도록 하자.

 

 물어보는 것은 $\sqrt[m]{a}+\sqrt[n]{b}$에 대해서만 물어보았지만 결국 정답이 A + B의 모든 영점이기 때문에 A의 모든 근과 B의 모든 근을 뭉탱이로 묶어서 생각하는 태도가 중요하며, 이를 위해 다음 행렬

 

$$\left[\begin{array}{ccccc}0& 0& \cdots & 0& a\\ 1& 0& \cdots & 0& 0\\ 0& 1& \cdots & 0& 0\\ ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& \cdots & 1& 0\end{array}\right]$$

 

 이 characteristic polynomial로 $x^m-a$를 가진다는 사실을 이용하기로 한다. 이제 우리가 필요한 것은 임의의 두 행렬 X, Y에 대해 X의 고유치들의 집합을 x, Y의 고유치들의 집합을 y라고 했을 때 x + y를 고유치들로 갖는 어떤 행렬 Z이며, 약간의 자료 조사를 통해 이런 행렬을 얻는 방법이 Kronecker Addition이라는 사실을 알 수 있다. (https://en.wikipedia.org/wiki/Matrix_addition) 결국 f, g를 각각 행렬 F, G로 변환하고, F와 G의 Kronecker sum에 해당하는 H를 구한 뒤, H의 characteristic polynomial을 구해주면 된다. 총 시간복잡도는 O((mn)^4)이다. characteristic polynomial은 위키피디아를 뒤져보면 정말 간단히 구현할 수 있는 알고리즘이 하나 있다(https://en.wikipedia.org/wiki/Faddeev%E2%80%93LeVerrier_algorithm). 이 알고리즘을 사용하면, 연산 과정에서 나눗셈이 들어가기는 하나 이 나눗셈의 결과가 항상 정수라는 것을 증명할 수 있으므로, long long을 사용하면 실수 오차 없이 구현할 수 있다.