Найбільший спільний дільник многочленів#5794

Найбільший спільний дільник многочленів

1 секунда

64 мегабайти

Дуже легка

Вчитель математики пан Мацудайра навчає своїх учнів розкладу та факторизації многочленів. Минулого тижня він доручив учням написати два многочлени (з однією змінною $x$ ) і знайти НСД (найбільший спільний дільник) цих многочленів як домашнє завдання, але йому стало нудно перевіряти їхні відповіді вручну. Тому вас просять написати програму для перевірки відповідей.

Розглядаються лише ті многочлени з цілими коефіцієнтами, які називаються цілими многочленами.

Коли дано два цілі многочлени $A$ і $B$ , цілий многочлен $C$ є спільним дільником $A$ і $B$ , якщо існують деякі цілі многочлени $X$ і $Y$ такі, що $A = C X$ A = CX і $B = C Y$ B = CY.

НСД двох цілих многочленів є спільним дільником, який має найвищий степінь (по $x$ ); вам потрібно написати програму, яка обчислює НСД двох многочленів.

Відомо, що НСД двох даних многочленів є унікальним, якщо ігнорувати множник-константу. Тобто, коли $C$ і $D$ є обидва НСД деяких двох многочленів $A$ і $B$ , $p \times C = q \times D$ p \times C = q \times D для деяких ненульових цілих чисел $p$ і $q$ .

Вхідні дані

Вхід складається з кількох наборів даних. Кожен набір даних складається з пари рядків введення, кожен з яких представляє многочлен як вираз, визначений нижче.

Первинний елемент — це змінна x, послідовність цифр $0$ – $9$ або вираз, укладений у дужки (...). Приклади: x, 99, (x+1).
Фактор — це первинний елемент сам по собі або первинний елемент, за яким слідує показник степеня. Показник степеня складається з символу ^, за яким слідує послідовність цифр $0$ – $9$ . Приклади: x^05, 1^15, (x+1)^3.
Член складається з одного або кількох прилеглих факторів. Приклади: 4x, (x+1)(x-2), 3(x+1)^2.
Вираз — це один або кілька членів, з'єднаних або +, або -. Крім того, перший член виразу може опціонально починатися зі знака мінус -. Приклади: -x+1, 3(x+1)^2-x(x-1)^2.

Цілі константи, показники степеня, множення (прилеглі), додавання (+) та віднімання/негування (-) мають свої звичайні значення. Послідовність цифр завжди інтерпретується як ціла константа. Наприклад, 99 означає $99$ , а не $9 \times 9$ 9 \times 9.

Будь-які підвирази введення, коли повністю розгорнуті та нормалізовані, мають коефіцієнти менші за $100$ і степені $x$ менші за $10$ . Послідовності цифр у показниках степеня представляють ненульові значення.

Усі набори даних розроблені так, щоб стандартний алгоритм з $32$ -бітними цілими числами з двійковим доповненням міг вирішити проблему без переповнень.

Кінець введення позначається рядком, що містить крапку.

Вихідні дані

Для кожного набору даних виведіть вираз многочлена НСД в одному рядку у форматі нижче.

$c_{0} x^{p_{0}} \pm c_{1} x^{p_{1}} \dots \pm c_{n} x^{p_{n}}$ c_0 x^{p_0} \pm c_1 x^{p_1} \ldots \pm c_n x^{p_n}

Де $c_{i}$ c_i і $p_{i}$ p_i ( $i = 0, \dots, n$ i = 0, \ldots, n) є додатними цілими числами з $p_{0} > p_{1} > \dots > p_{n}$ p_0 > p_1 > \ldots > p_n, і найбільший спільний дільник ${c_{i} ∣ i = 0, \dots, n}$ \{c_i | i = 0, \ldots, n\} дорівнює $1$ .

Додатково:

Коли $c_{i}$ c_i дорівнює $1$ , його слід опустити, якщо відповідний $p_{i}$ p_i не дорівнює $0$ ,
$x^{0}$ x^0 слід опустити повністю, і
$x^{1}$ x^1 слід записати як x.

Приклади

Приклад 1