デバッグ出力消し損ねて900がTLEしました。
とても悲しいです。
900解法
とりあえず求めるものは、1+直線の数+Σ(各交点で交わってる直線の数-1)
双対変換すると、直線たちはa×bのグリッド上の点になる。
交わる→同一直線上にある、となるので意味のありそうな直線に関して全部調べれば良い。
傾きが同じものはいっぺんに処理できそうなので、αy=βx+? (α=1~a-1,β=-(b-1)~b-1,αとβは互いに素) の直線について全部調べれば良い。β=1~b-1の時を数えて適当に二倍とかすると傾きが正のものだけを考えるだけですむ。
傾きを決めた時にΣ(直線上の点の数-1)をO(1)で求めたい。
傾きを決めると、(x mod α, y mod β)ごとに独立になる。独立させた点たちもまた長方形な感じに並んでるから、x*y-x-y+1で余裕。長方形の形として考えられるのも(±1,±1)の範囲の４通りしかないし余裕。
しかし、なんかO(1)のパートをいろいろ考えながらやった痕跡の謎な処理群が僕のコードには入っていてムダ感が半端ない。
