Atcoder Beginner Contest 306 - ABC 306 G - Return to 1 の解法です．
問題概要
$N$ 頂点 $M$ 辺の有向グラフがある． 頂点 $1$ から辺をたどることをちょうど $10^{10^{100}}$ 回繰り返して 頂点 $1$ に戻ってくることが可能か判定せよ． テストケース $T$ 個．
制約: $T \leq 2 \times 10^5$． $N$ の総和と $M$ の総和は $2 \times 10^5$ 以下．
コンテスト中の経緯
まず，強連結成分分解をして，頂点1を含む強連結成分のみを 考えれば良い．
頂点 1 から出発して戻ってくるサイクルの長さ全部の集合を $C$， $C$ の最大公約数を $g$ とする． $10^{10^{100}}$ は十分大きいので， $g \mid 10^{10^{100}}$ であることが， $10^{10^{100}}$ が $C$ の要素の非負整数倍の和で表せることと同値になる． $g \mid 10^{10^{100}}$ は，もちろん， $g$ が $2$ と $5$ 以外の素因数を持たないことと同値である．
ということで，$g$ を求めれば良いのだが，$C$ は 巨大な集合なので直接には求められない． なんらかの $C$ の部分集合で，最大公約数が $g$ と等しくなるようなものを 求めるのだろうと思った．すべての辺について， それを使うサイクルは少なくとも 1 回は評価しないといけないであろうという ことで，根拠薄弱だが，次のような集合を取ってみることにした．
$C’ := \{ \text{dist}(1, x) + 1 + \text{dist}(y, 1) \mid (x, y) $ はグラフの辺 $\}$
ここで，$\text{dist}(x, y)$ は，2頂点 $x$, $y$ 間の距離である． $\text{GCD}(C’)$ が $2$ と $5$ 以外の素因数を持たないかどうかで Yes / No を答えるようにした．
ダメ元で提出してみたが，ジャッジが詰まっていて， コンテスト終了までに結果が返ってこなかった． 結局このつまりが原因で ABC306 は unrated になった． コンテスト終了後に TLE が帰ってきたが，最初の強連結成分分解で， 頂点 $1$ が単独成分になる場合の考慮漏れだった． これを直したら AC になった．
証明
コンテスト後， 公式解説 を見たら，想定解法は上の解法と少し似ていた． それを読んでしばらく考えたところ，上の解法も正当であることがわかった．
主張1 任意の辺 $(x, y)$ に対して， $g \mid (\text{dist}(1, x) + 1 + \text{dist}(y, 1))$．
主張2 $a$ を正の整数とする． 任意の辺 $(x, y)$ に対して $a \mid (\text{dist}(1, x) + 1 + \text{dist}(y, 1))$ であれば， 頂点1からの任意のサイクルの長さは，$a$ の倍数である．
主張1, 2 から，$C$ と $C’$ の公約数の集合が一致することがわかるので， $g = \text{GCD}(C’)$ である．
(主張1の証明) 頂点$1$から頂点$x$への最短パスと辺$(x, y)$ と 頂点 $y$ から頂点 $1$ への最短パスをつなぐと，長さ $\text{dist}(1, x) + 1 + \text{dist}(y, 1)$ のサイクルになる． $g$ はこういうものたちの公約数であった．(終)
(主張2の証明) 正の整数 $a$ をとる． 任意の辺 $(x, y)$ に対して $a \mid (\text{dist}(1, x) + 1 + \text{dist}(y, 1))$ と仮定する． このとき，$1 = x_1, x_2, x_3, \ldots$ が頂点1を出発するパスであれば， $\text{dist}(1, x_i) \equiv i - 1 \pmod a,\quad \text{dist}(x_i, 1) \equiv 1 - i \pmod a$ であることを帰納法で示す． これが示せれば，$x_k = 1$ であれば $k \equiv 1 \pmod a$ である． つまり，サイクルの長さは $a$ の倍数である．
$i = 1$ は自明．$i$までOKとすると， 辺 $(x_i, x_{i + 1})$ に関して， $\text{dist}(1, x_i) + 1 + \text{dist}(x_{i + 1}, 1) \equiv 0$ だから， 帰納法の仮定より $\text{dist}(x_{i + 1}, 1) \equiv i$．
$\text{dist}(1, x_{i + 1})$ については， もし $x_{i + 1} = 1$ なら $i \equiv 0, \quad\text{dist}(1, x_{i + 1}) = 0 \equiv i$ でOKなので，$x_{i + 1} \neq 1$ とする．$x_{i + 1}$ から $1$ への 最短パス上で，$x_{i + 1}$ の隣の点を $y$ とすると， $0 \equiv \text{dist}(1, x_{i + 1}) + 1 + \text{dist}(y, 1) \equiv \text{dist}(1, x_{i + 1}) + 1 + (i - 1)$ より， $\text{dist}(1, x_{i + 1}) \equiv i$．(終)
まあ，証明はできたものの，公式解説の方法の方がずっと良い．