Общий многочлен
Учитель математики, господин Мацудайра, обучает своих учеников разложению и факторизации многочленов. На прошлой неделе он дал задание написать два многочлена (с одной переменной x) и в качестве домашнего задания определить НОД (наибольший общий делитель) этих многочленов. Однако проверять их ответы вручную ему показалось скучным, поэтому он попросил вас создать программу для проверки результатов.
Рассматриваются только многочлены с целыми коэффициентами, которые называются целыми многочленами.
Если даны два целых многочлена A и B, то целый многочлен C является их общим делителем, если существуют такие целые многочлены X и Y, что A = CX и B = CY.
НОД двух целых многочленов — это общий делитель, имеющий наивысшую степень (по x). Ваша задача — написать программу, которая вычисляет НОД двух многочленов.
Известно, что НОД двух данных многочленов уникален, если игнорировать постоянный множитель. То есть, если C и D оба являются НОД двух многочленов A и B, то p×C = q×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×9.
Любые подвыражения входных данных, когда они полностью разложены и нормализованы, имеют коэффициенты меньше 100 и степени x меньше 10. Последовательности цифр в показателях степени представляют ненулевые значения.
Все наборы данных разработаны так, чтобы стандартный алгоритм с 32-битными целыми числами в дополнительном коде мог решить задачу без переполнений.
Конец ввода обозначается строкой, содержащей точку.
Выходные данные
Для каждого набора данных выведите многочлен НОД в строке в формате ниже.
c_0x^p_0 ± c_1x^p_1...± c_nx^p_n
Где c_i и p_i (i = 0, ..., n) — положительные целые числа с p_0 > p_1 > ... > p_n, и наибольший общий делитель {c_i | i = 0, ..., n} равен 1.
Дополнительно:
Когда c_i равно 1, оно должно быть опущено, если соответствующее p_i не равно 0,
x^0 должно быть опущено полностью, и
x^1 должно быть записано как x.