ABC210E - Ring MST

解答の補足事項のみ書いておく．

以下では，$l, m,n\in \mathbb{Z}$とする．

はじめに$A_{i_{1}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は

\begin{aligned}
& x + l A_{i_{1}} \pmod N \\
& \Leftrightarrow x + l A_{i_{1}} + m N
\end{aligned}

である．ユークリッドの互除法 - Wikipediaを思い出せば，これは

\begin{aligned}
& x + n \gcd (N, A_{i_{1}})
\end{aligned}

と同値である．

次に$A_{i_{2}}$を選び，辺を張れるだけ張ったすると，$x$と同じ連結成分にできる頂点は

\begin{aligned}
& x + l\gcd (N, A_{i_{1}}) + m A_{i_{2}} \\
& \Leftrightarrow x + n\gcd(\gcd (N, A_{i_{1}}), A_{i_{2}})
\end{aligned}

と表せる．$\gcd(a, b, c) = \gcd( \gcd(a, b), c)$であるから，結局

\begin{aligned}
& x +n \gcd(N, A_{i_{1}}, A_{i_{2}})
\end{aligned}

となる．

以上を帰納的に繰り返すと，次がわかる．

結果1.

$A_{i_{1}}, A_{i_{2}},...,A_{i_{k}}$を選んだとき，$x$と同じ連結成分にできる頂点の集合は

\begin{aligned}
&\{x + n \gcd(A_{i_{1}}, A_{i_{2}},...,A_{i_{k}}) \pmod N \mid n \in \mathbb{Z} \} \\
&= \{x + n \gcd(N, A_{i_{1}}, A_{i_{2}},...,A_{i_{k}}) \mid n \in \mathbb{Z} \} \\
&\qquad \cap \{0,1, ... , N - 1\}
\end{aligned}

である．

次に，$A_{i_{1}}, A_{i_{2}},...,A_{i_{k}}$を選んだときの連結成分の個数を求めたい．そのためには，上の集合の要素数で$N$を割れば良い．ここで，集合

\begin{aligned}
S(x, m)
& = \{x + n m \pmod N \mid n \in \mathbb{Z} \}
\end{aligned}

の要素数は，

\begin{aligned}
&|S(x, m)| = |S(0, m)| \\
&=\frac{\mathrm{lcm}(N,m)}{m} \\
&= \frac{Nm/\gcd(N,m)}{m} \\
&= N / \gcd(N,m)
\end{aligned}

となる．これにより，$m=\gcd(A_{i_{1}}, A_{i_{2}},...,A_{i_{k}})$のときの連結成分の個数は

\begin{aligned}
N / |S(x, m)|
&= \gcd(N,m) \\
&= \gcd(N, A_{i_{1}}, A_{i_{2}},...,A_{i_{k}})
\end{aligned}

となる．