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

対称性により、\(R\gt U\) の場合も同様に扱えるため、一般性を失わずに \(R\leq U\) と仮定します。さらに、\(0\leq y\leq R\) の場合と \(R\lt y\leq U\) の場合に分けて考えます。

\(0\leq y\leq R\) の場合、格子点 \((x, y)\) は \(\max(x,y)\) が偶数であるとき黒で塗られています。

\(0\) 以上 \(R\) 以下の偶数 \(k\) に対し、\(\max(x, y)=k\) となる格子点は \(x=k\) または \(y=k\) を満たします。

• \(x=k\) の場合、\(y\) は \(0\) 以上 \(k\) 以下の値を取ることができるため、格子点の個数は \(k+1\) である。
• 同様に、\(y=k\) の場合でも格子点の個数は \(k+1\) である。

\((k, k)\) が二重に数えられているので、重複を除くと合計で \(2k+1\) 個となります。

\(R\) 以下の最大の偶数を \(p\) とすると、黒の格子点の総数は、\(k\in\{0, 2, \dots, p\}\) に対する格子点の合計になります。

区間 \([0, R]\) に含まれる偶数 \(k\) は \(\frac{p}2+1\) 個あるので、等差数列の和の公式を用いると、黒の格子点の総数は

\[ \begin{aligned} &\quad(2\cdot0+1)+(2\cdot2+1)+\dots+(2\cdot p+1) \\ &=\frac{(\frac{p}2+1)(2p+2)}2 \\ &=\left(\frac{p}2+1\right)(p+1) \end{aligned} \]

となります。

\(R\lt y\leq U\) の場合、\(0\leq x\leq R\lt y\) により \(y=\max(x,y)\) となるため、格子点の色は \(y\) の偶奇のみに依存します。

各 \(y\) に対して \(R+1\) 個の格子点があるので、区間 \((R, U]\) に含まれる偶数の個数を \(q\) として、黒の格子点の個数は \(q(R+1)\) で表せます。

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

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

実装例 (Python)