Сторона вчителя математики
Одним із завдань, які студенти регулярно виконують на уроках математики, є розв'язання поліноміального рівняння. Наприклад, маючи поліном X^2 − 4X + 1, потрібно знайти його корені (2 ± ).
Якщо завдання студентів полягає в тому, щоб знайти корені заданого полінома, то завдання вчителя полягає в тому, щоб знайти поліном, який має заданий корінь. Пані Гальсоне - захоплена вчителька математики, яка втомилася від пошуку розв'язків квадратних рівнянь, які є такими простими, як a + b. Вона хотіла створити рівняння вищого ступеня, розв'язки яких є трохи складнішими. Як зазвичай у задачах на уроках математики, вона хоче зберегти всі коефіцієнти цілими числами і зберегти ступінь полінома якомога меншим (за умови, що він має заданий корінь). Будь ласка, допоможіть їй, написавши програму, яка виконує завдання з боку вчителя.
Вам дано число t у вигляді:
t = +
де a і b - різні прості числа, а m і n - цілі числа, більші за 1.
У цій задачі вам потрібно знайти мінімальний поліном на цілих числах для t, який є поліномом
F(X) = a_dX^d + a_{d−1}X^{d−1} + · · · + a_1X + a_0
що задовольняє наступні умови.
Коефіцієнти a_0, ..., a_d є цілими числами і a_d > 0.
F(t) = 0.
Ступінь d є мінімальним серед поліномів, що задовольняють дві попередні умови.
F(X) є примітивним. Тобто, коефіцієнти a_0, ..., a_d не мають спільних дільників, більших за один.
Наприклад, мінімальний поліном для + на цілих числах - це F(X) = X^4−10X^2+1. Перевірка F(t) = 0 є такою ж простою, як і наступна (α = , β = ).
F(t) = (α + β)^4 − 10(α + β)^2 + 1
= (α^4 + 4α^3β + 6α^2β^2 + 4αβ^3 + β^4) − 10(α^2 + 2αβ + β^2) + 1
= 9 + 12αβ + 36 + 8αβ + 4 − 10(3 + 2αβ + 2) + 1
= (9 + 36 + 4 − 50 + 1) + (12 + 8 − 20)αβ = 0
Перевірка того, що ступінь F(t) є насправді мінімальним, є трохи складнішою. На щастя, за умовою, даною в цій задачі, а саме, що a і b - різні прості числа, а m і n більші за один, ступінь мінімального полінома завжди дорівнює mn. Більше того, він завжди є моном. Тобто, коефіцієнт його найвищого степеня (a_d) дорівнює одиниці.
Вхідні дані
Вхід складається з кількох наборів даних, кожен у наступному форматі.
a m b n
Цей рядок представляє m + n. Останній набір даних супроводжується одним рядком, що складається з чотирьох нулів. Числа в одному рядку розділені одним пробілом.
Кожен набір даних задовольняє наступні умови.
m
+ n
≤ 4.
mn ≤ 20.
Коефіцієнти відповіді a_0, ..., a_d знаходяться в межах від (−2^31 + 1) до (2^31 − 1), включно.
Вихідні дані
Для кожного набору даних виведіть коефіцієнти його мінімального полінома на цілих числах
F(X) = a_dX^d + a_{d−1}X^{d−1} + ··· + a_1X + a_0,
у наступному форматі.
a_d a_{d−1} ... a_1 a_0
Ненегативні цілі числа повинні бути надруковані без знака (+ або −). Числа в одному рядку повинні бути розділені одним пробілом, і жодні інші символи або зайві пробіли не повинні з'являтися у виході.