Сторона вчителя математики

Одним із завдань, які студенти регулярно виконують на уроках математики, є розв'язання поліноміального рівняння. Наприклад, маючи поліном X^2 - 4X + 1, потрібно знайти його корені (2 \pm \sqrt{3}).

Якщо завдання студентів полягає в тому, щоб знайти корені заданого полінома, то завдання вчителя полягає в тому, щоб знайти поліном, який має заданий корінь. Пані Гальсоне - захоплена вчителька математики, яка втомилася від пошуку розв'язків квадратних рівнянь, які є такими простими, як a + b. Вона хотіла створити рівняння вищого ступеня, розв'язки яких є трохи складнішими. Як зазвичай у задачах на уроках математики, вона хоче зберегти всі коефіцієнти цілими числами і зберегти ступінь полінома якомога меншим (за умови, що він має заданий корінь). Будь ласка, допоможіть їй, написавши програму, яка виконує завдання з боку вчителя.

Вам дано число $t$ у вигляді:

де $a$ і $b$ - різні прості числа, а $m$ і $n$ - цілі числа, більші за $1$.

У цій задачі вам потрібно знайти мінімальний поліном на цілих числах для $t$, який є поліномом

що задовольняє наступні умови.

1. Коефіцієнти a_0, ..., a_d є цілими числами і a_d > 0.

2. F(t) = 0.

3. Ступінь $d$ є мінімальним серед поліномів, що задовольняють дві попередні умови.

4. $F(X)$ є примітивним. Тобто, коефіцієнти a_0, ..., a_d не мають спільних дільників, більших за один.

Наприклад, мінімальний поліном для \sqrt{2} + \sqrt{3} на цілих числах - це F(X) = X^4-10X^2+1. Перевірка F(t) = 0 є такою ж простою, як і наступна (\alpha = \sqrt{3}, \beta = \sqrt{2}).

Перевірка того, що ступінь $F(t)$ є насправді мінімальним, є трохи складнішою. На щастя, за умовою, даною в цій задачі, а саме, що $a$ і $b$ - різні прості числа, а $m$ і $n$ більші за один, ступінь мінімального полінома завжди дорівнює $mn$. Більше того, він завжди є монічним. Тобто, коефіцієнт його найвищого степеня (a_d) дорівнює одиниці.