灘文化祭コン2022day2-I-Product of LCM of GCDを解いた感想

問題:I - Product of LCM of GCD (atcoder.jp)
提出コード:提出 #31593529 - 灘校文化祭コンテスト 2022 Day2 (atcoder.jp)

　問題文を要約すると, 数列 $${A}$$ が与えられるのでそれらの重複含めた並び替えすべてについて, 要素を $${K}$$ 個ごとに分割し各区間ごとの $${GCD}$$ をとった後にそれらの $${LCM}$$ の総積を求めればいいです.

　まず, スコアが $${i}$$ の倍数になるような順列の数を求め, それらを利用してうまくかけ合わせせることを考えます. 
具体的には, スコアが $${i}$$の倍数になる順列の数を $${m}$$とすると, 
$${i}$$の素因数が1つの時 $${{i}^{m}}$$ を, それ以外の時は $${1}$$
をかければよいです.
これはスコアを素因数分解することで, 簡単にわかります.
また, スコアが $${i}$$ の倍数になるような順列の数を求めるのにかかる計算量を $${O(X)}$$ とすると, 数列 $${A}$$ の $${K}$$ 個未満の要素にしか含まれない素因数は求める値に影響しないので, 適切に前計算をしておくことで, $${O(\frac{XN}{K})}$$ で求められることが分かります. 
　次にスコアが$${i}$$の倍数になるような順列の数を求めることを考えます.
 $${A}$$の要素のうち$${i}$$の倍数であるもののの個数を $${x}$$とすると, $${\frac{N}{K}}$$ 個の区間のうち, $${j}$$個以上が$${i}$$の倍数であるような順列の数は
$${{}_x {C}_{jK} (jK)! {}_{\frac{N}{K}} {C}_{j}(N-jK)!}$$
であるので, 包除することで前計算を除いて$${O(K)}$$で求められます.
よってこの問題を$${O(N)}$$で解くことができました.