まず、題意を満たす3点の選び方を考えるのではなく、3点が一直線上に並ぶような選び方を全体から引くことを考えます。

\(X\) や \(Y\) が等しい場合は予め取り除き、 \(X_1 < X_2 < X_3\) 、 \(Y_1 < Y_2 < Y_3\) と仮定します。（ \(Y_1 > Y_2 > Y_3\) の場合も対称性より同様）

ここで、 \(X_3 - X_1\) と \(gcd(X_3 - X_2, X_2 - X_1)\) を固定して考えると、

① \(X_1\) の候補は \(H - (X_3 - X_1)\) 通り

② \(X_3 - X_2 : X_2 - X_1 = Y_3 - Y_2 : Y_2 - Y_1\) より、 \(Y_3 - Y_1\) は \((X_3 - X_1) / gcd(X_3 - X_2, X_2 - X_1)\) の倍数

③ \(Y_3 - Y_1\) の候補それぞれに対し、それに対応する \(Y_1\) の候補は \(W - (Y_3 - Y_1)\) 通り

④ \(X_2\) の候補は、上記の固定した値を満たすものの個数

⑤ \(Y_2\) の値は、\(X_3 - X_2 : X_2 - X_1 = Y_3 - Y_2 : Y_2 - Y_1\) より上の4つを定めた時点で一意に定まる

となるので、②③は等差数列の和となり \(O(1)\) で、④は約数包除により \(X_3 - X_1\) の値ごとに \(O(d(x)^2)\) で求めることができます。（ \(d(x)\) で \(x\) の約数の個数を表す）以上より、\(N = min(H,W)\) として全体で \(O(NlogNd(x))\) で求めることができます。 \(d(x)\) はこの制約上で最大128になり、およそ\(2.2×10^8\)の計算が必要になるように見えますが、実際はこれよりも遥かに高速に動作します。