ARMERIA

Rubyと競技プログラミングの話　AtCoderやCodeforcesの問題解説記事が多め。

Waseda University Programming Contest 2020 E: LCM Count (AOJ 3155)

AOJ プログラミング競技プログラミング

お題箱より。

Aizu Online Judge

解法

最小公倍数や最大公約数は、素因数ごとに「重複度の最大値/最小値」を取るという観点で捉えると考えやすくなることがあります。

$A_{0}, ..., A_{k-1}$ の最小公倍数（LCM）は、全ての素数 $p_{i}$ について各要素における $p_{i}$ の重複度の最大値 $c_{i}$ を求め、 $p_{i}^{c_{i}}$ を全て掛け合わせたものである。
$A_{0}, ..., A_{k-1}$ の最大公約数（GCD）は、全ての素数 $p_{i}$ について各要素における $p_{i}$ の重複度の最小値 $c_{i}$ を求め、 $p_{i}^{c_{i}}$ を全て掛け合わせたものである。

この観点で問題を捉えるために、まず $N$ を素因数分解します。 $N$ の相異なる素因数を $p_{1}, ..., p_{n}$ とし、それぞれの重複度を $c_{1}, ..., c_{n}$ とします。

整数列 $A$ の要素のLCMが $N$ になる必要十分条件は、以下の条件を全て満たすことです。

の全ての要素はの約数である。すなわちの全ての要素について以下が成り立つ。
- 素因数として $p_{1}, ..., p_{n}$ 以外の素数が登場しない。
- 全ての $N$ の素因数 $p_{i}$ について、その重複度が $c_{i}$ 以下である。
全てのの素因数について以下が成り立つ。
- $A$ の少なくとも1つの要素について、素因数 $p_{i}$ の重複度がちょうど $c_{i}$ である。

この条件を満たす数列を数える上で、「 $A$ の全ての要素は $N$ の約数である」という点は前提とします。その上で「 $A$ の少なくとも1つの要素について、素因数 $p_{i}$ の重複度がちょうど $c_{i}$ である」という条件は扱いにくいので、包除原理を適用します。

$\lbrace 1, ..., n\rbrace$ の部分集合 $s$ について、 $C(s)$ を以下の条件を満たす数列の個数と定義します。包除原理から答えは $\sum_{s} (-1)^{|s|}C(s)$ と計算できます。

相異なる $N$ の約数からなる、空でない数列である。
$s$ に属するインデックス $i$ について、素因数 $p_{i}$ の重複度が $c_{i}$ である要素が存在しない。

この $C(s)$ を求めましょう。まず数列の要素として使える整数が何種類あるのかを計算します。これはそれぞれの素因数 $p_{i}$ について、取り得る重複度が何通りあるのかを以下のように求めて、全て掛け合わせたものです。

$i$ が $s$ に属している場合、取り得る重複度は $0, ..., c_{i}-1$ の $c_{i}$ 通り。
$i$ が $s$ に属していない場合、取り得る重複度は $0, ..., c_{i}$ の $c_{i}+1$ 通り。

この値を $M$ とすると、 $C(s)$ は $M$ 種類の整数から $1$ 種類以上を選んで並べた数列の個数です。これは数列の長さごとに分けて考えると、

長さ $1$ ： $_{M}P_{1} = \frac{M!}{(M-1)!}$ 通り
長さ $2$ ： $_{M}P_{2} = \frac{M!}{(M-2)!}$ 通り
$\cdots$
長さ $M$ ： $_{M}P_{M} = \frac{M!}{0!}$ 通り

と計算することができて、この総和は $M!\times(\frac{1}{0!} + \frac{1}{1!} + \cdots + \frac{1}{(M-1)!})$ とまとめられます。これは階乗と階乗の逆元の累積和を前計算しておけば $O(1)$ で計算できます。

これで $C(s)$ が計算できるので、包除原理の式に従って答えを求めることができます。

計算量は素因数分解パートと階乗前計算パートが $O(\sqrt{N})$ 、包除原理パートが $N$ の相異なる素因数の個数 $n$ に対して $O(n2^{n})$ です。 $1 \le N \le 10^{12}$ のとき $0 \le n \le 11$ なので十分間に合います。

ACコード

Aizu Online Judge