\(P_i\) を \(A_i\) を素因数分解したときの素因数の列とする. ただし, 同じ素因数が複数個含まれる場合はそれらを区別する. たとえば, \(A_i = 24\) のときは, \(P_i = \{ 2_1, 2_2, 2_3, 3_1 \}\) という感じである.

こうすることで, gcd は積集合を, lcm は和集合を計算する操作となる.

\(N = 5\) のときは,

初期状態:

\[(P_1, P_2, P_3, P_4, P_5)\]

1回目の操作後:

\[(P_1 \cap P_2, P_2 \cup P_3, P_3 \cap P_4, P_4 \cup P_5)\]

2回目の操作後:

\[((P_1 \cap P_2) \cap (P_2 \cup P_3), (P_2 \cup P_3) \cup (P_3 \cap P_4), (P_3 \cap P_4) \cap (P_4 \cup P_5)) = (P_1 \cap P_2, P_2 \cup P_3, P_3 \cap P_4)\]

となり, 以下同様に操作していくと, 最終的には \(P_1 \cap P_2\) が残る. すなわち, 最後に残る数は \(\gcd(A_1, A_2)\) である. これが \(M\) になる組み合わせの数を求めればいい.

これは \(iM, jM\) (\(1 \leq i, j \leq N/M\), \(i, j\) は互いに素) となる \(i, j\) の個数である.

\(i\) を固定すれば, \(j\) は \(i\) の素因数を含まない値の個数であり, 包除原理を使って求めることができる. \(N \leq 10^5\) なので素因数の種類は高々6つであり計算量も問題はない.

最後に \(A_3\) 以降はどう並べてもいいので, \((N-2)!\) を掛ける.