yukicoder No.2264 Gear Coloring - かんプリンの学習記録

問題概要
解説
提出プログラム
感想

問題概要

歯車が ${N}$ 個あり，歯車 ${i}$ は ${A_i}$ 枚の歯を持つ．歯車 ${i}$ と歯車 ${i+1}$ が噛み合っている．これらの歯車の歯に ${M}$ 色の色を塗る方法は何通りあるか．ただし，回転によって一致する色の塗り方を同一視する．

${1\leq N\leq 10^3}$
${1\leq M < 998244353}$
${3\leq A_i < 998244353}$
${\operatorname{lcm}(A_1, A_2, \dots, A_N) < 998244353}$

解説

ポリアの数え上げ定理(バーンサイドの補題)より， ${L=\operatorname{lcm}(A_1, A_2, \dots, A_N)}$ として

${\displaystyle\frac{\sum_{d=1}^{L}M^{\sum_{i=1}^{N}\gcd(d,A_i)}}{L}}$
が答えとなります．
${1\leq d\leq L}$ に対して ${\gcd(d,L)}$ が同じとなる ${d}$ は ${\sum_{i=1}^{N}\gcd(d,A_i)}$ が同じ値になるのでまとめることができて，