Задача 579
Точки решетки в решеточных кубах

Решеточный куб - это куб, чьи все вершины имеют целочисленные координаты. Пусть C(n) будет количеством различных решеточных кубов, координаты вершин которых находятся в диапазоне от 0 до n (включительно). Здесь два куба считаются различными, если координаты не всех их вершин совпадают.
Например, C(1)=1, C(2)=9, C(4)=100, C(5)=229, C(10)=4469 и C(50)=8154671.

Различные кубы могут содержать разное количество точек решетки.

Например, куб с вершинами
(0, 0, 0), (3, 0, 0), (0, 3, 0), (0, 0, 3), (0, 3, 3), (3, 0, 3), (3, 3, 0), (3, 3, 3) содержит 64 точки решетки (56 точек решетки на поверхности, включая 8 вершин, и 8 точек внутри куба).

В свою очередь, куб с вершинами
(0, 2, 2), (1, 4, 4), (2, 0, 3), (2, 3, 0), (3, 2, 5), (3, 5, 2), (4, 1, 1), (5, 3, 3) содержит только 40 точек решетки (20 точек на поверхности и 20 точек внутри куба), хотя оба куба имеют одинаковую длину ребра 3.

Пусть S(n) будет суммой точек решетки, содержащихся в различных решеточных кубах, координаты всех вершин которых находятся в диапазоне от 0 до n (включительно).

Например, S(1)=8, S(2)=91, S(4)=1878, S(5)=5832, S(10)=387003 и S(50)=29948928129.

Найдите S(5000) mod 109.

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