Mujin Programming Challenge 2018:D - うほょじご
問題
解法
(x, y) の組をグラフ上の1つの頂点に対応させて考える.(x, y) に1回操作してなる数の組 (tx, ty) から (x, y) に辺を張る.そうすると,(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる.このような組を DFS でフラグを付けて数えてあげて,全体の組の数 N*M から引くことで無限ループになる組の数を計算できる.O(999*999).
解答
整数問題だったので,規則性を何とか見出そうとして嘘解法で WA を出していて詰まっていた.解説を見て,グラフに帰着させるとシンプルに解けると分かった.