1 / 1

403:放物線と直線で囲まれた格子点

整数 $a$ と $b$ に対し、放物線 $y = x^2$ と直線 $y = ax + b$ で囲まれた領域 $D(a, b)$ を定義しよう。すなわち： $D(a, b) = \{ (x, y) \,|\, x^2 \leq y \leq ax + b \}$

$D(a, b)$ に含まれる格子点の個数を $L(a, b)$ と定義しよう。例として、 $L(1, 2) = 8, L(2, -1) = 1$ である。

さらに $D(a, b)$ の面積が有理数であり、かつ $|a|, |b| \leq N$ であるすべてのペア $(a, b)$ に対する $L(a, b)$ の和を $S(N)$ と定義する。 $S(5) = 344, S(100) = 26709528$ であることが確認できる。

$S(10^{12})$ を求めよ。回答は $10^8$ を法として答えよ。

整数 $a$ と $b$ に対し、放物線 $y = x^2$ と直線 $y = ax + b$ で囲まれた領域 $D(a, b)$ を定義しよう。すなわち： $D(a, b) = \{ (x, y) \,|\, x^2 \leq y \leq ax + b \}$

$D(a, b)$ に含まれる格子点の個数を $L(a, b)$ と定義しよう。例として、 $L(1, 2) = 8, L(2, -1) = 1$ である。

$S(10^{12})$ を求めよ。回答は $10^8$ を法として答えよ。