\(L=D=0\)（かつ \(R, U\geq0\)）を満たす部分問題について考えます。求めたいのは \(0\leq x\leq R\) かつ \(0\leq y\leq U\) を満たす格子点 \((x, y)\) の個数です。

一般性を失わずに \(R\leq U\) と仮定します。部分問題をさらに \(0\leq y\leq R\) の場合と \(R\lt y\leq U\) の場合に分けます。

• \(0\leq y\leq R\) の場合、\(c_1\) を区間 \([0, R]\) に含まれる偶数の個数として、黒い格子点の個数は等差数列の和の形で \(\frac{c_1(1+4c_1-3)}2=c_1(2c_1-1)\) となります。これは数学的帰納法によって証明できます。
• \(R\lt y\leq U\) の場合、\(0\leq x\leq R\lt y\) により \(y=\max(|x|, |y|)\) となるため、格子点の色は \(y\) の偶奇のみに依存します。各 \(y\) の値に対して格子点は \(R+1\) 個あるので、黒い格子点の個数は \(c_2(R+1)\) で表せます。ここで \(c_2\) は区間 \((R, U]\) に含まれる偶数の個数です。

以上より、\(L=D=0\) を満たす部分問題に対する黒い格子点の個数が求められます。

元の問題は、対称性と包除原理を組み合わせて、上記の部分問題に帰着できます。時間計算量は \(O(1)\) です。

実装例 (Python)