Здравствуйте, Аноним, Вы писали:
А>это я не в ту степь. А>про phi это просто гипотеза была о том как примерно устроены такие многочлены. не обращайте внимания.
А>Помоему для вашей задачи чисто практически достаточно уже приведённого решения = А>проверить F в точках [0.. min(K, D-1)] по модулю D.
А>Если хочется поразнообразней, то можно факторизовать D чтоб получить разложение в простые, но это уже само по себе может быть достаточно громоздким. А>И тогда тут уже можно воспользоваться простой проверкой коэффициентов многочлена для каждого простого числа из разложения. А>При этом для степеней простых в разложении мне так и непонятна хорошая формула. так что для них всё равно вычислять F в диапазоне придётся.
Большое Спасибо Вам, Буравчику и dilmah за ответы.
Провел ещё консультации по этой задаче с математиками в университете, и хотелось бы подвести итог дискуссии:
1.В вариантах полинома когда D мало, подставляем в полином значения n от 0 до D-1. Если на всём этом диапазоне результат целое число — значит для
любого положительного n результат выражения всегда будет целым числом.
2.В вариантах полинома когда D велико, но мала степень необходимо вычислить значение полинома в точках Е+1 (где Е-максимальная степень полинома)
Например для полинома (2n^3+3n^2+n)/6 необходимо провести вычисления подставляя n от 1 до 4 (потомучто максимальная степень = 3).
Если на всём этом диапазоне результат целое число — значит для любого положительного n результат выражения всегда будет целым числом.
Оба варианта решения универсальны. Вар.1 применяем когда D мало но велика макс.степень. Вар.2 применяем когда D велико, но мала макс. степень.
