교사가 푸는 수학

학생들이 수학 시간에 흔히 하는 일 중 하나는 다항식 방정식을 푸는 것이다. 즉 어떤 다항식, 예를 들어 $X^2 - 4X + 1$이 주어졌을 때 그 근 $2 \pm \sqrt{3}$을 찾는 것이다.

학생의 과제가 주어진 다항식의 근을 찾는 것이라면, 교사의 과제는 주어진 근을 갖는 다항식을 찾는 것이다. 열정적인 수학 교사 Galsone 선생님은 $a + b\sqrt{c}$처럼 단순한 이차방정식의 해를 구하는 데 싫증이 났다. 그래서 해가 조금 더 복잡한 고차 방정식을 만들고 싶어 한다. 수학 시간 문제가 으레 그렇듯, 그는 모든 계수를 정수로 유지하고 (주어진 근을 갖는다는 조건 아래) 다항식의 차수를 가능한 한 작게 하고 싶어 한다. 교사의 과제를 수행하는 프로그램을 작성해 그를 도와라.

다음 형태의 수 $t$가 주어진다.

$t = \sqrt[m]{a} + \sqrt[n]{b}$

여기서 $a$와 $b$는 서로 다른 소수이고, $m$과 $n$은 $1$보다 큰 정수이다.

당신은 $t$의 정수 위의 최소 다항식을 찾아야 한다. 즉 다음 조건을 만족하는 다항식 $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$를 찾는 것이다.

1. 계수 $a_0, \dots, a_d$는 정수이고 $a_d > 0$이다.
2. $F(t) = 0$이다.
3. 위 두 조건을 만족하는 다항식 중 차수 $d$가 최소이다.
4. $F(X)$는 원시적이다(primitive). 즉 계수 $a_0, \dots, a_d$는 $1$보다 큰 공약수를 갖지 않는다.

예를 들어 $\sqrt{3} + \sqrt{2}$의 정수 위 최소 다항식은 $F(X) = X^4 - 10X^2 + 1$이다. $F(t) = 0$을 확인하는 것은 다음처럼 간단하다($\alpha = \sqrt{3}$, $\beta = \sqrt{2}$로 두자).

$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$

$F$의 차수가 실제로 최소임을 확인하는 것은 조금 더 어렵다. 다행히 이 문제의 조건 — $a$와 $b$가 서로 다른 소수이고 $m, n$이 $1$보다 큼 — 아래에서는 최소 다항식의 차수가 항상 $mn$이다. 또한 항상 모닉(monic)이다. 즉 최고차항의 계수 $a_d$가 $1$이다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

a m b n

이 줄은 $\sqrt[m]{a} + \sqrt[n]{b}$를 나타낸다. 마지막 데이터셋 다음에는 네 개의 $0$으로 이루어진 한 줄이 온다. 한 줄 안의 수들은 공백 하나로 구분된다.

모든 데이터셋은 다음 조건을 만족한다.

1. $\sqrt[m]{a} + \sqrt[n]{b} \le 4$.
2. $mn \le 20$.
3. 답의 계수 $a_0, \dots, a_d$는 $-231 + 1$ 이상 $231 - 1$ 이하이다.

입력은 여러 개의 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.

a m b n

이 줄은 $\sqrt[m]{a} + \sqrt[n]{b}$를 나타낸다. 마지막 데이터셋 다음에는 네 개의 $0$으로 이루어진 한 줄이 온다. 한 줄 안의 수들은 공백 하나로 구분된다.

모든 데이터셋은 다음 조건을 만족한다.

1. $\sqrt[m]{a} + \sqrt[n]{b} \le 4$.
2. $mn \le 20$.
3. 답의 계수 $a_0, \dots, a_d$는 $-231 + 1$ 이상 $231 - 1$ 이하이다.

각 데이터셋에 대해, 정수 위 최소 다항식 $F(X) = a_d X^d + a_{d-1} X^{d-1} + \cdots + a_1 X + a_0$의 계수를 다음 형식으로 출력한다.

ad ad-1 ... a1 a0

음이 아닌 정수는 부호($+$ 또는 $-$) 없이 출력해야 한다. 한 줄 안의 수들은 공백 하나로 구분해야 하며, 출력에 그 밖의 문자나 여분의 공백이 나타나서는 안 된다.