天才か！！！

問題概要

$N$ 個の整数 $a_1, a_2, \dots, a_N$ が与えられる。 $1 \le i$ < $j \le N$ となる $i, j$ であって、LCM( $a_i, a_j$ ) が最小となるものを求めよ。

制約

$1 \le N \le 10^{6}$
$1 \le a_i \le 10^{7}$

考えたこと

$a_i \le 10^{7}$ という制約がいかにも怪しい。この制約が意味するのは

配列 a をバケットで表せる。すなわち a = (2, 3, 5) みたいな配列を b = (0, 0, 1, 1, 0, 1) みたいに表せる。

ということ。この性質をとても利用しそうな雰囲気がある。この性質を利用したいなと思うと、

$a$ のうち $k$ の倍数を全部挙げてなんかする

ということをやりたくなる。少し考えてみると、 ${\rm GCD}(a_i, a_j)$ としてありうる値は高々 $10^{7}$ 通りしかないことがわかる。この値で場合分けして考えてみよう。

最大公約数の値で場合分け

${\rm GCD}(a_i, a_j) = k$ のとき、 $k$ の倍数だけ列挙して考えれば良い。そして $k$ の倍数のうち、小さい順に 2 個とって、「その積 / $k$ 」を求めてあげれば良い。ここで、実際にはその小さい順にとった 2 個の最大公約数が $k$ ではなく $k$ より大きな $k$ の倍数になる可能性もあるが、そのようなケースも結局探索されるので気にしなくて良い。

計算量は、 $A = 10^{7}$ として、各 $k$ に対して $\frac{A}{k}$ だけ調べることになるので、 $O(A\log{A})$ となる。

#include <iostream>
#include <vector>
using namespace std;
const int MAX = 10101010;

int main() {
    vector<int> num(MAX, 0);
    int N; cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i], num[a[i]]++;

    long long res = 1LL<<60;
    long long ares, bres;
    for (int k = 1; k < MAX; ++k) {
        vector<long long> vals;
        for (int i = k; i < MAX; i += k) {
            if (!num[i]) continue;
            for (int j = 0; j < min(num[i], 2); ++j) vals.push_back(i);
        }
        if (vals.size() < 2) continue;
        long long lcm = vals[0]/k * vals[1];
        if (res > lcm) res = lcm, ares = vals[0], bres = vals[1];
    }

    int i, j;
    for (i = 0; i < N; ++i) if (a[i] == ares) break;
    for (j = 0; j < N; ++j) if (a[j] == bres && j != i) break;
    if (i > j) swap(i, j);
    cout << i+1 << " " << j+1 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces 552 DIV3 G. Minimum Possible LCM (R2400)

問題概要

制約

考えたこと

最大公約数の値で場合分け