Codeforces #613 (Div. 2) F. Classical? (R2800)

勉強になった...けど、これ知らずにできるもんなの！？

問題へのリンク

あと、LCM の最小値バージョンもある！

drken1215.hatenablog.com

問題概要

個の正の整数 が与えられる。これらから 2 個選んで LCM をとってできる 個の整数の最大値を求めよ。

制約

• 
• 

考えたこと

という制約がいかにもそれっぽい。LCM ってのはなかなかに考えづらいから、ここは GCD を固定して考えることにする。つまり

• GCD の値が となるような 2 数についての LCM の最大値

を各 について求めていくことにする。 なのでいい感じ。さて、考察対象を の倍数に絞ったとき、それらの中から「互いに素」な 2 つの整数の積として考えられる最大値を求めたい。

まずこの手の問題でよくあることとして、数列 をバケットで管理しておくことにする。つまり

• a'[ ] := 数列 の中に という値があるかどうか

という配列として管理する。こうすることで、 を抜き取る作業を でできるのだ ( を登場する値の最大値とする)。 で合計したとき、 となる。

g の倍数に関する問題

問題は 個の値 から互いに素な 2 整数の積の最大値を考える問題に帰着された。

注目したいこととして、

• が互いに素であったとき、 の相方として より小さいものは考えなくてよい

ということ。当たり前のことなのだが、たったこれだけでかなり枝刈りができる。以下のようにする。

---

• 大きい順に値を見ていってスタックに入れる
• 今見ている値が であるとき、スタックの中に と互いに素な値があるならば、スタックの中で最小の値を破棄してよい

---

その理由は、もしスタックの中に値 が存在してそれが と互いに素であるならば、

• から見て より小さい値を考慮する必要がないため、 のことは今後一切考えなくてもよいので を捨てることができる
• スタックにある値のうち より小さい値については、今後 より小さい値としか結びつく可能性がないため、同様に捨てることができる

という感じ。結局、どの要素もスタックに 1 回だけ入れられて、1 回だけ削除されるような感じになる。すごくこどふぉっぽい計算量評価の仕組みだ！！！！！！！

残る問題は「スタックの中に と互いに素な整数があるかどうか」をどうやって高速に判定するかだ。そういうことができるデータ構造を設計しよう。

やりたいこと

やりたいことは以下の操作のできるデータ構造を設計すること。登場する値の最大値は 程度であるとする。

1. 値 を挿入する
2. 値 を削除する
3. データ構造の中に値 と互いに素なものが何個あるかを求める (存在判定だけでよいけど、個数も求められる)

これを実現するために、以下のデータを管理する。

• counter[ ] := データ構造の中に の倍数が何個あるか

の挿入は、 のすべての約数 に対して counter[ ] をインクリメントすればよい。 の削除は、 のすべての約数 に対して counter[ ] をデクリメントすればよい。最後に と互いに素なものの個数は、

で求められる。 はメビウス関数。そしてこれらのクエリを処理するためには

• の約数列挙
• に対するメビウス関数の値

を前処理しておく。これらはエラトステネスの篩によってできる。

計算量

整数 の約数の個数の最大値を とする。結局計算量は、「約数の個数分」だけの時間のかかる処理を 回やる感じになるので、 みたいな感じになると思う。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

// isprime[n] := is n prime?
// mebius[n] := mebius value of n
// min_factor[n] := the min prime-factor of n
struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> mebius;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      mebius(MAX+1, 1),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            mebius[i] = -1;
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if ((j / i) % i == 0) mebius[j] = 0;
                else mebius[j] = -mebius[j];
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factors(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }

    // enumerate divisors
    vector<int> divisors(int n) {
        vector<int> res({1});
        auto pf = prime_factors(n);
        for (auto p : pf) {
            int n = (int)res.size();
            for (int i = 0; i < n; ++i) {
                int v = 1;
                for (int j = 0; j < p.second; ++j) {
                    v *= p.first;
                    res.push_back(res[i] * v);
                }
            }
        }
        return res;
    }
};



long long GCD(long long x, long long y) {
    if (y == 0) return x;
    return GCD(y, x % y);
}

const int MAX = 110000;

int main() {
    Eratos er(MAX);
    vector<vector<int>> divs(MAX);
    for (int n = 1; n < MAX; ++n) divs[n] = er.divisors(n);

    stack<int> st;
    vector<int> counter(MAX, 0);
    auto push = [&](int x) {
        st.push(x);
        for (auto d : divs[x]) ++counter[d];
    };
    auto pop = [&]() {
        int x = st.top();
        st.pop();
        for (auto d : divs[x]) --counter[d];
    };
    auto count = [&](int x) {
        int res = 0;
        for (auto d : divs[x]) res += er.mebius[d] * counter[d];
        return res;
    };

    int N;
    cin >> N;
    vector<long long> a(N);
    vector<bool> isin(MAX+1, false);
    long long res = 0;
    for (int i = 0; i < N; ++i) {
        cin >> a[i];
        res = max(res, a[i]);
        isin[a[i]] = true;
    }

    for (int g = 1; g < MAX; ++g) {
        for (int v = (MAX/g)*g; v >= g; v -= g) {
            if (!isin[v]) continue;
            while (count(v/g)) {
                long long t = st.top() * g;
                res = max(res, t / GCD(v, t) * v);
                pop();
            }
            push(v/g);
        }
        while (!st.empty()) pop();
    }
    cout << res << endl;
}