余事象を考えることにします．

\((X_{3}-X_{1},Y_{3}-Y_{1})=(h,w)\) とすると， \((X_{1},Y_{1})\) と \((X_{3},Y_{3})\) の候補は \((H-h)(W-w)\) 個あり，これを決め打てば \((X_{2},Y_{2})\) の候補は \(\gcd (h,w) -1\) 個あります．

よって， \((H-1,H-2, \ldots 1)\) と \((W-1 , W-2, \ldots 1)\) を \(\gcd\) 畳み込みすれば良いです．

計算量は \(O(\min (H,W) \log \log \min (H,W))\) になります．

提出

また， \(\mathrm{dirichlet}\) 級数の累積和としても解釈ができるので， \(N=\min(H,W)\) として， \(O(N^{\frac{2}{3}})\) であったり，分母が疎であることを利用して \(O(\sqrt{N} \log ^{2} N)\) にもなります．