人権なし

競プロで解いた問題や開発の進捗などの記録です

Mujin Programming Challenge 2018:D - うほょじご

問題

beta.atcoder.jp

解法

(x, y) の組をグラフ上の1つの頂点に対応させて考える.(x, y) に1回操作してなる数の組 (tx, ty) から (x, y) に辺を張る.そうすると,(x, 0) と (0, y) から到達できる組はいつか操作が終了する組だと分かる.このような組を DFS でフラグを付けて数えてあげて,全体の組の数 N*M から引くことで無限ループになる組の数を計算できる.O(999*999).

解答

beta.atcoder.jp

整数問題だったので,規則性を何とか見出そうとして嘘解法で WA を出していて詰まっていた.解説を見て,グラフに帰着させるとシンプルに解けると分かった.

f:id:babcs2035:20181030220803p:plain