https://kanpurin.hatenablog.com/entry/2023/04/09/000046

問題概要

歯車が ${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)}$ が同じ値になるのでまとめることができて，

${\displaystyle\frac{\sum_{d|L}M^{\sum_{i=1}^{N}\gcd(d,A_i)}\times\phi(L/d)}{L}}$

となり，高速に求めることができます．

提出プログラム

https://yukicoder.me/problems/no/2264/submissions

感想

何を使うかは問題文から明らかですが，まとめることに気付くのが難しい？