Задача 269
Полиномы, имеющие хотя бы одно целое решение

Корнем или нулем полинома P(x) является решение уравнения P(x) = 0.
Определим Pn как полином, коэффициентами которого являются цифры числа n.
К примеру, P5703(x) = 5x3 + 7x2 + 3.

Нетрудно увидеть, что:

  • Pn(0) является последней цифрой n,
  • Pn(1) является суммой всех цифр n,
  • Pn(10) является самим числом n.

Определим Z(k) как количество положительных целых чисел n, не превышающее k, для которого у полинома Pn есть по крайней мере одно целое решение.

Можно показать, что Z(100 000) равно 14696.

Чему равно Z(1016)?

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net