ARMERIA

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

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

お題箱より。

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 になる必要十分条件は、以下の条件を全て満たすことです。

  1.  A の全ての要素は  N の約数である。すなわち  A の全ての要素について以下が成り立つ。
    • 素因数として  p_{1}, ..., p_{n} 以外の素数が登場しない。
    • 全ての  N の素因数  p_{i} について、その重複度が  c_{i} 以下である。
  2. 全ての  N の素因数  p_{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