Pashen, определение этого многочлена рекурсивное и содержит немного магии, но идея там простая.
P(x, n) = p1*x^0 + p2*x^1 + ... pn*x^n =
1. P(x, n) = P(x, n) + p1*x^0 + p2*x^1 + ... pn*x^n, p1,p2,...,pn - целые числа.
2. P(x, n) = (1/a) * mul(P(x,a)+i, i=0..a-1) * P(x, n-a), a - натуральное число > 1, b - целое число.
Первая строка в пояснении не нуждается, линейная комбинация целых чисел - целое число.
Со второй строкой похитрее. Докажем сначала, что коэффициенты искомого многочлена рациональные. Доказательство рациональности можно выполнить при помощи рассмотрения n+1 различных целых значений x, составить систему из n+1 уравнений относительно p0...pn, по построению матрица системы содержит только целые числа, как вектор неизвестных, поэтому по формуле Крамера ее решение рационально.
Пусть коэффициент pk - рациональный, по определению pk=c/d - несократимая дробь, c - целое число, d - натуральное. Тогда многочлен P(x,n) представим в виде P(x,n) = (1/d) * Q(x,n), где Q(x,n) - многочлен с рациональными коэффициентами. Произведение двух рациональных чисел будет целым, если одно из них нацело делится на обратное к другому. Т.е. задача сводится к поиску такого многочлена Q(x,n) c рациональными коэффициентами, который делится на натуральное число d при любых целых x. Заметим, что произведение любых k последовательных целых чисел делится на k, т.к. хотя бы одно из них делится на k. Тогда для делимости многочлена Q(x,n) на d при любых целых x необходимо и достаточно, чтобы Q(x,n) можно было представить в виде Q(x,n) = S(x,d)*(S(x,d)+1)*(S(x,d)+2)*...*(S(x,d)+d-1) * R(x,n-d). Отсюда следует, что если коэффициент pk - рациональный, то многочлен P(x,n) = (1/d) * S(x,d)*(S(x,d)+1)*(S(x,d)+2)*...*(S(x,d)+d-1) * R(x,n-d) - целый, если многочлены S(x,d) и R(x,n-d) - целые.
Таким образом задача свелась к задачам с меньшей размерностью. Поэтому можно определить вид многочлена P(x,n) рекурсивно по новой формуле.