次をみたす整数組 \((x,y,z)\) の個数を求めればよいです．

• \(0\leq x,y\leq N\)
• \(Ax+By+Cz=0\)

\(g:=\gcd(B,C)\) として \(By_0+Cz_0=g\) なる \(y_0,z_0\) を拡張 Euclid の互除法であらかじめ求めておきます．また \(B^\prime:=B/g,C^\prime:=C/g\) とします．

\(x\) を固定したとき，\(By+Cz=-Ax\) となります． これは \(Ax\) が \(g\) の倍数，すなわち \(x\) が \(\dfrac{g}{\gcd(A,g)}(=:m)\) の倍数であるときのみ解を持ち，\(A^\prime:=\dfrac{A}{\gcd(A,g)},x=mt\) とおけば，解は整数 \(k\) を用いて \[y=C^\prime k-A^\prime y_0t,\quad z=-B^\prime k-A^\prime z_0t\] と表せます．このうち \(0\leq y\leq N\) をみたすものの個数は \[\left\lfloor\dfrac{N+A^\prime y_0t}{C^\prime}\right\rfloor-\left\lceil\dfrac{A^\prime y_0t}{C^\prime}\right\rceil+1\] 個です．これを \(0\leq t\leq\lfloor N/m\rfloor\) について足し合わせた値を求められればよく，それは floor sum を用いれば高速に計算できます．