Допустим, у вас есть два многочлена и . Тогда многочлен можно единственным образом представить в виде

Это может быть сделано делением в столбик. В этой записи обозначает степень многочлена P(x). при этом будем называть остатком от деления многочлена на многочлен и обозначать .

Раз есть способ разделить один многочлен на другой с остатком, то можно определить и алгоритм Евклида для нахождения наибольшего общего делителя двух многочленов. Алгоритм определён таким образом, что он принимает пару многочленов , а затем если многочлен нулевой, то алгоритм возвращает многочлен , а иначе возвращает результат выполнения алгоритма для пары . На каждом шаге степень второго аргумента уменьшается, поэтому алгоритм отработает за конечное число шагов. Но насколько большим оно может быть? Это вам и предстоит выяснить.

Вам дано число n. Вам нужно вывести два многочлена степени не выше n таких, что их коэффициенты — целые числа, не превышающие 1 по абсолютной величине, при этом старший коэффициент (при максимальной степени x) должен быть равен единице, и вычисление их наибольшего общего делителя потребует ровно n шагов алгоритма Евклида. Кроме того, степень первого многочлена должна быть больше степени второго. Шагом алгоритма Евклида мы называем переход от к .