Задача 403
Точки сетки, заключенные между параболой и прямой

Для целых a и b определим D(a, b) как область, ограниченную параболой y = x2 и прямой y = a·x + b:
D(a, b) = { (x, y) | x2ya·x + b }.

L(a, b) определено как количество точек единичной сетки, заключенных в D(a, b).
Например, L(1, 2) = 8 и L(2, -1) = 1.

Определим также S(N) как сумму L(a, b) для всех пар (a, b) таких, что площадь D(a, b) является рациональным числом и |a|,|b| ≤ N.
Можно показать, что S(5) = 344 and S(100) = 26709528.

Найдите S(1012). Дайте ваш ответ mod 108.

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