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