Задача 274
Множители делимости

Для любого целого числа p > 1, являющегося взаимно простым числу 10, существует положительный множитель делимости m < p, благодаря которому сохраняется делимость на p для следующей функции любого натурального переменного n:

f(n) = (все цифры n, кроме последней) + (последняя цифра n) * m

Т.е., если m является множителем делимости на p, то f(n) делится на p без остатка тогда и только тогда, когда n делится на p без остатка.

(Если n намного больше p, то f(n) будет меньше, чем n и повторное применение формулы f создает мультипликативную проверку делимости на p).

К примеру, множитель делимости на 113 равен 34.

f(76275) = 7627 + 5 * 34 = 7797: 76275 и 7797 делятся на 113 без остатка
f(12345) = 1234 + 5 * 34 = 1404: 12345 и 1404 не делятся на 113 без остатка

Сумма множителей делимости, которые являются взаимно простыми числами с 10 и не превышают 1000, равна 39517. Чему равна сумма множителей делимости, которые являются взаимно простыми числами с 10 и не превышают 107?

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