No.644

$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)!$ を掛ける.