Codeforces Round #613 (Div. 2) F - Classical?
問題概要
$n$ 個の整数からなる数列 $A$ が与えられるので、$\mathrm{lcm} (A_i, A_j)$の最大値を求めよ。
(問題では添字が相異なるという条件がついていますが、$\mathrm{lcm} (a, a) = a \leq \mathrm{lcm} (a, x)$なので問題ありません。)
- $ 2 \le n \le 10^{5} $
- $ 1 \le A_{i} \le 10^{5} $
問題を変形する
まず、LCMは扱いづらいので、$ \displaystyle \mathrm{lcm} (a, b) = \frac{a}{\gcd (a, b) } \cdot b $ と変換します。
このとき、$ \displaystyle \frac{a}{\gcd (a, b) } $と $ b $ は互いに素になるので、あらかじめ数列に$ a $ の約数全てを加えておくことにすると、次のような問題に帰着できます。
- 互いに素な 要素2つの積の最大値を求めよ。
これでだいぶ見通しがよくなりました。
うまく候補を絞る
2つの要素を選んで何かを求める問題では、片方を全探索すると解ける場合が多いです。このテクニックはこの問題でも有効で、小さい方を全探索するとよいです。
以下、$A$は昇順に並んでいるとします。
$A_i$を$i$の大きい方から見ていきます。まずは愚直に探索してみると、次のようになります。
- $A_j (i < j)$を全探索し、$\gcd(A_i, A_j) = 1$ ならば $A_i A_j$で答えを更新する。
これは当然間に合いませんが、$A_i$を降順に見ているため、次のループから$A_j$として見るのはこの次の要素からでよいことがわかります。
しかしこれでも、互いに素な要素がない場合に、すべての組を見ることになってしまい間に合いません。
包除原理で高速化
これを高速化するためには、次のクエリに高速に答えられればよいです。
- 数列に$x$を追加する。
- 数列から$x$を削除する。
- 数列のうち、$x$と互いに素な要素の数を求める。
これは、包除原理を使えば解くことが出来ます。「互いに素」の余事象を考えると、「$x$と共通な素因数を少なくとも1つ持つ」となります。
$x$が持つ素因数を$p_1, p_2, \ldots , p_k $とすると、上の3つのクエリは、$ \lbrace p_1, p_2, \ldots , p_k \rbrace $のすべての部分集合$S$について、
- 追加/削除のとき、$cnt [Sの要素の総積]$に1を加算/減算する
- 求値クエリのとき、$ (-1)^{|S|} cnt [Sの要素の総積] $の総和を求める
とすれば、$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 \geq 10^{5} $より、異なる素因数の個数は6以下なので、十分高速です。
ACコード
備考
包除原理パートは、次の問題が参考になります。（というよりも、ほぼ同じです）