この問題は中国剰余定理 の練習問題です。

中国剰余定理とは？

長さ \(N\) の整数組 \((r_i, m_i)\) が与えられたとき、 \(0\) 以上 \(\mathrm{LCM}(m_1,m_2,\ldots,m_N)\) 未満の整数 \(x\) であって、

• \(x \bmod m_i = r_i\ (1\leq i \leq N)\)

を満たすものが \(m_i\) が互いに素な場合一意に定まるという定理です。

例えばAtCoder Library を用いると、一意に定まるときそのような \(x\) を \(\mathrm{O}(N\log(\mathrm{LCM}(m_1,m_2,\ldots,m_N)))\) で求めることが出来ます。

本問題の解説

\(A\) について、 \(i\to A_i\) の辺を貼ったグラフを考えたとき、長さ \( c\) のサイクルがあれば \(B\) から \(N\bmod {c}\) が特定できることに着目しましょう。

一番最初に思い付く方針としてはサイクルの長さとして \(2,3,5,\ldots,23,29\) (\(29\) 以下の素数全体) を採用すれば \(\mathrm{LCM}(2,3,5,\ldots,23,29) = 6469693230 \geq 10^9\) より \(N\) が中国剰余定理から復元できますが、残念ながら \(2+3+5+\ldots+23+29=129 > 110\) より \(M\) の制約をオーバーしてしまいます。

ここでサイクルの長さとして \(4,9,5\ldots,19,23\) を採用すると、\(\mathrm{LCM}(4,9,5,\ldots,19,23) =1338557220 \geq 10^9\) かつ \(4+9+5+\ldots+19+23=108 \leq 110\) より \(N,M\) 両方の条件を満たし、AC することができます。