お題箱より。
解法
最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。
の最小公倍数(LCM)は、全ての素数
について各要素における
の重複度の最大値
を求め、
を全て掛け合わせたものである。
の最大公約数(GCD)は、全ての素数
について各要素における
の重複度の最小値
を求め、
を全て掛け合わせたものである。
この観点で問題を捉えるために、まず を素因数分解します。
の相異なる素因数を
とし、それぞれの重複度を
とします。
整数列 の要素のLCMが
になる必要十分条件は、以下の条件を全て満たすことです。
の全ての要素は
の約数である。すなわち
の全ての要素について以下が成り立つ。
- 素因数として
以外の素数が登場しない。
- 全ての
の素因数
について、その重複度が
以下である。
- 素因数として
- 全ての
の素因数
について以下が成り立つ。
の少なくとも1つの要素について、素因数
の重複度がちょうど
である。
この条件を満たす数列を数える上で、「 の全ての要素は
の約数である」という点は前提とします。その上で「
の少なくとも1つの要素について、素因数
の重複度がちょうど
である」という条件は扱いにくいので、包除原理を適用します。
の部分集合
について、
を以下の条件を満たす数列の個数と定義します。包除原理から答えは
と計算できます。
- 相異なる
の約数からなる、空でない数列である。
に属するインデックス
について、素因数
の重複度が
である要素が存在しない。
この を求めましょう。まず数列の要素として使える整数が何種類あるのかを計算します。これはそれぞれの素因数
について、取り得る重複度が何通りあるのかを以下のように求めて、全て掛け合わせたものです。
が
に属している場合、取り得る重複度は
の
通り。
が
に属していない場合、取り得る重複度は
の
通り。
この値を とすると、
は
種類の整数から
種類以上を選んで並べた数列の個数です。これは数列の長さごとに分けて考えると、
- 長さ
:
通り
- 長さ
:
通り
- 長さ
:
通り
と計算することができて、この総和は とまとめられます。これは階乗と階乗の逆元の累積和を前計算しておけば
で計算できます。
これで が計算できるので、包除原理の式に従って答えを求めることができます。
計算量は素因数分解パートと階乗前計算パートが 、包除原理パートが
の相異なる素因数の個数
に対して
です。
のとき
なので十分間に合います。