Problem 4580. ABCDEF - ICPC突破専用ザク

サークルで久々にSPOJの問題を解いたので解法をメモっておく．

問題

https://www.spoj.pl/problems/ABCDEF/

You are given a set S of integers between -30000 and 30000 (inclusive).
Find the total number of sextuples $(a,b,c,d,e,f);a,b,c,d,e,f\in S,d\neq 0$ that satisfy:
$\frac{ab-c}{d}-e=f$

異なる整数の集合Sが与えられるので，それに対して上式を満たすようなa,b,c,d,e,f∈Sの組はいくつあるか答えよ，という問題．
集合Sの大きさは $\sharp S\le 100$ を満たす．

解法

以下解法書くので解法見ずに解きたい人とか注意．
まず全探索をすると $\Theta(n^6)$ かかって時間内に終わらない．
そこで，上の数式を同値変形して，
$ab-c=d(e+f) (d\neq 0)$ のようにする．
このとき左辺のとりうる値の重複を込めた集合 $T=\{ab-c;a,b,c\in S\}$ をとって，ソートする．
すると(d,e,f)の値を定めたとき等号が成り立つような(a,b,c)の組の個数は，右辺の値でTを2分探索すれば分かることになる．
（ここで探索するときに $d\neq 0$ であることに気をつける．）

よって， $\Theta(n^3\log{n})$ の計算量で解を求めることができる．