解説において、閉路の長さの最大公約数を考えていますが、これはペロン＝フロベニウスの定理（Wikipedia）に関係する概念としては周期と呼ばれるものです。そのため、周期を求めればこの問題が解けるという事実を、ペロン＝フロベニウスの定理の結果に帰着してみます。 また、フロベニウス数（Wikipedia）も関係があると思われるため、こちらについても紹介します。

ペロン=フロベニウスの定理は非負の実正方行列に関する定理であるため、まずはこの問題を非負の実正方行列に関する問題に言い換えます。

この問題では、「今居る頂点から出ている辺を任意に選び、その辺に沿って移動する操作」を考えていますが、この操作の代わりに「今居る頂点から出ている辺のうちの1つを確率的に選び、その辺に沿って移動する操作」を考えます。ただし、出次数が\(0\)である頂点があると確率が定義し難いため、全ての頂点で出次数は\(1\)以上とします。また、頂点\(1\)が含まれる強連結成分に含まれない頂点を考える必要はないため、強連結であることも仮定します。

このように考えるとこの問題は、「頂点\(1\)に居る状態から上の操作を\(n\)回繰り返したときに頂点\(1\)に居る確率が正であるか」を判定する問題となります。ただし\(n=10^{10^{100}}\)とします。どの頂点に居るかを表す確率分布を確率ベクトルとして考えると、上の操作は確率行列\(P\)として表すことができるため、\(P^{n}\)の\(1\)行目\(1\)列目の成分が正であることを判定する問題だと考えることもできます。これで、非負の実正方行列の問題に言い換えることができました。

次にペロン＝フロベニウスの定理に関係する概念をいくつか紹介します。

ある性質をもつ非負の実正方行列を既約と呼びます。定義はいくつかありますが、この問題に即して言えば、「元となった有向グラフが強連結」であることと同値と考えて良いです。上で書いた通り強連結であることを今回は仮定しているため、\(P\)は既約だと言えます。

次に頂点\(1\)の周期を考えます。これは、頂点1から始まり頂点1で終わる（長さ\(1\)以上の）パスの長さの最大公約数として定義されます。解説に書かれている\(G\)の定義と異なりますが、Wikipedia にも書かれている通り、既約（強連結）であればどの頂点に関する周期も同じ値になるため、実はこの周期と解説に書かれた\(G\)は同じ値になります。よって以降は\(G\)を頂点\(1\)の周期とします。

\(G\)が\(1\)であるとき、\(P\)は非周期的（aperiodic）と言います。また、（既約という前提のもとで）同値な概念である原始的という言葉を使うこともあります。

さて、\(G\)は頂点1から始まり頂点1で終わるパスの長さの最大公約数として定義していたため、\(P^{k}\)の\(1\)行目\(1\)列目の成分が正であるためには\(k\)が\(G\)の倍数である必要があります。つまり、\(G\)が\(n\)の約数でないときはNoが答えです。逆に\(n\)が\(G\)の倍数であるときにどうなるのかを、以下で見ていきます。

まず\(G=1\)のとき、すなわち非周期的（原始的）な場合を考えます。ペロン＝フロベニウスの定理のメインの結果ではありませんが、これもWikipedia に書かれている通り、ある\(k\)が存在して\(P^{k}\)の全ての成分が正となります。また、\(P\)は既約（強連結）であったため、その\(k\)より大きい任意の整数\(k^{\prime}\)について\(P^{k^{\prime}}\)が正であることがわかります。つまり十分大きな\(k\)について、\(P^{k}\)は常に正となります。Wikipedia によると、少なくとも\(N^{2}-2N+2\)以上であれば必ず正となるようです。\(n\)はこれより明らかに大きいため、\(G=1\)のときYesとなることがわかりました。

また、\(G=1\)のとき、十分大きな\(k\)に対して\(P^{k}\)が常に正となるというのは、最大公約数が\(1\)のときは必ずフロベニウス数が存在することからも想像ができます。

次に\(G \neq 1\)かつ\(G\)が\(n\)の約数のときについて考えます。このときは、元のグラフにおいて長さがちょうど\(G\)であるパスで到達できる頂点に対して辺を引いたグラフを考えて、そのグラフにおける頂点\(1\)の強連結成分を考えれば、\(G=1\)の場合に帰着できると思います。つまり\(P^{G}\)を考えたうえで既約となる部分を抜き出すということです。\(G\)は\(N\)以下であるため、この場合についても\(n\)が十分大きいことがわかり、Yesであることが言えます。