[백준 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의 모든 근을 뭉탱이로 묶어서 생각하는 태도가 중요하며, 이를 위해 다음 행렬

 

$$ \begin{bmatrix} 0 & 0 & \cdots & 0 & a \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1  & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & 0 \end{bmatrix} $$

 

 이 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을 사용하면 실수 오차 없이 구현할 수 있다.