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)$$なので問題ありません。)

まず、LCMは扱いづらいので、$$ \displaystyle \mathrm{lcm} (a, b) = \frac{a}{\gcd (a, b) } \cdot b $$ と変換します。

このとき、$$ \displaystyle \frac{a}{\gcd (a, b) } $$と $$ b $$ は互いに素になるので、あらかじめ数列に$$ a $$ の約数全てを加えておくことにすると、次のような問題に帰着できます。

これでだいぶ見通しがよくなりました。

2つの要素を選んで何かを求める問題では、片方を全探索すると解ける場合が多いです。このテクニックはこの問題でも有効で、小さい方を全探索するとよいです。

以下、$$A$$は昇順に並んでいるとします。

$$A_i$$を$$i$$の大きい方から見ていきます。まずは愚直に探索してみると、次のようになります。

$$A_j \ (i < j)$$を全探索し、$$\gcd(A_i, A_j) = 1$$ ならば $$A_i A_j$$で答えを更新する。

これは当然間に合いませんが、$$A_i$$を降順に見ているため、次のループから$$A_j$$として見るのはこの次の要素からでよいことがわかります。

しかしこれでも、互いに素な要素がない場合に、すべての組を見ることになってしまい間に合いません。

これを高速化するためには、次のクエリに高速に答えられればよいです。

これは、包除原理を使えば解くことが出来ます。「互いに素」の余事象を考えると、「$$x$$と共通な素因数を少なくとも1つ持つ」となります。

$$x$$が持つ素因数を$$p_1, p_2, \ldots , p_k $$とすると、上の3つのクエリは、$$ \lbrace p_1, p_2, \ldots , p_k \rbrace $$のすべての部分集合$$S$$について、

とすれば、$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 \geq 10^{5} $$より、異なる素因数の個数は6以下なので、十分高速です。

包除原理パートは、次の問題が参考になります。（というよりも、ほぼ同じです） codeforces.com