Задача 606
Цепи Гозинта II
Цепью Гозинта для числа n называется последовательность {1,a,b,...,n}, где каждый элемент делится на предыдущий без остатка.
Например, существует восемь различных цепей Гозинта для числа 12:
{1,12}, {1,2,12}, {1,2,4,12}, {1,2,6,12}, {1,3,12}, {1,3,6,12}, {1,4,12} и {1,6,12}.
Пусть S(n) будет суммой всех чисел k, не превышающих n, которые имеют 252 различных цепей Гозинта.
Известно, что S(106)=8462952 и S(1012)=623291998881978.
Найдите S(1036) и приведите в качестве ответа последние девять цифр полученного значения.
© Проект Эйлера | Translated problems from ProjectEuler.net