CF 1285F Classical?

题目描述

https://codeforces.com/problemset/problem/1285/F

简要题意：给定一个长度为 $n$ 的序列 $a_i$，求 $max_{1\le i<j\le n}lcm(a_i,a_j)$

$n,a_i\le 10^5$

Solution

注意到 $a_i$ 的值域很小，我们考虑一个针对值域的做法，首先我们把所有 $a_i$ 的约数都求出来，令其为集合 $S$，那么最终的答案一定为从 $S$ 中选出两个互质的数的最大 $lcm$，我们考虑二分 $lcm$，那么如果 $\sum_{x\in S}\sum_{y\in S}[(x,y)=1][xy\ge lcm]$，按照莫比乌斯反演的套路，我们得到 $\sum_{d\in S}\mu(d)\sum_{d|x}\sum_{d|y}[xy\ge lcm]$，我们枚举 $d$，后面枚举 $x$ 之后是一个双指针，总时间复杂度为 $O(n\log^2 n)$

其实这题还有一个 $O(n\log n)$ 的做法，我们还是考虑对 $S$ 求 $lcm$，我们维护一个栈，从大到小加入数 $x$，如果栈中存在一个 $y$ 与 $x$ 互质，那么对于 $x<z<y$，$z$ 一定没用了，因为我们现在的答案至少是 $xy$，而后面加入的数 $w$ 与 $z$ 的答案至多是 $wz<xy$，所以我们可以一直弹栈顶直到栈中不存在与 $x$ 互质的数，那么我们如何判断是否存在于 $x$ 互质的数呢？答案还是莫反，我们有 $\sum_{y\in S}[(x,y)=1]=\sum_{d|x}\mu_d cnt_d$，其中 $cnt_d$ 表示有多少数是 $d$ 的倍数，这个东西可以在入栈和出栈时顺便维护，时间复杂度 $O(n\log n)$

#include <iostream> // 单 log
#include <vector>
#include <stack>
#include <algorithm>
#include <numeric>
#define maxn 100010
#define ll long long
using namespace std;

int pri[maxn], mu[maxn]; bool isp[maxn]; vector<int> D[maxn];
void init_isp(int n) {
    mu[1] = 1; int cnt = 0; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i];
        }
    }
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) D[j].push_back(i);
}

int n, cnt[maxn];
bool vis[maxn];

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; vector<int> a;
    for (int i = 1, x; i <= n; ++i) cin >> x, vis[x] = 1;
    n = 100000;
    for (int i = 1; i <= n; ++i) { 
        for (int j = i; j <= n; j += i) vis[i] |= vis[j];
        if (vis[i]) a.push_back(i);
    } sort(a.begin(), a.end(), greater<int>()); 
    n = *max_element(a.begin(), a.end()); init_isp(n); stack<int> S; ll ans = 1;
    for (auto x : a) {
        int res = 0; 
        for (auto d : D[x]) res += mu[d] * cnt[d];
        while (!S.empty() && res) {
            int y = S.top(); S.pop();
            for (auto d : D[y]) { 
                if (x % d == 0) res -= mu[d];
                --cnt[d];
            } if (gcd(x, y) == 1) ans = max(ans, 1ll * x * y); 
        }
        for (auto d : D[x]) ++cnt[d]; S.push(x);
    } cout << ans << "\n";
    return 0;
} 

#include <iostream> // 双 log
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;

int pri[maxn], cnt, mu[maxn]; bool isp[maxn]; 
void init_isp(int n) {
    mu[1] = 1; 
    for (int i = 2; i <= n; ++i) {
        if (!isp[i]) pri[++cnt] = i, mu[i] = -1;
        for (int j = 1; j <= cnt && i * pri[j] <= n; ++j) {
            isp[i * pri[j]] = 1;
            if (i % pri[j] == 0) break;
            mu[i * pri[j]] = -mu[i];
        }
    }
}

int n, a[maxn];

vector<int> A[maxn]; bool vis[maxn];
int check(ll x) {
    ll ans = 0; 
    for (int i = 1; i <= n; ++i) {
        if (!vis[i] || !mu[i]) continue; int m = A[i].size(); ll res = 0; 
        for (int j = 0, k = m - 1; j < m; ++j) {
            while (k > 0 && 1ll * A[i][k - 1] * A[i][j] >= x) --k;
            if (1ll * A[i][k] * A[i][j] >= x) res += m - k;
        } ans += mu[i] * res;
    } return ans > 0 ;
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 1, x; i <= n; ++i) cin >> x, vis[x] = 1;
    n = 100000; init_isp(n);
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i) vis[i] |= vis[j];
    for (int i = 1; i <= n; ++i) 
        for (int j = i; j <= n; j += i) if (vis[j]) A[i].push_back(j);
    ll l = 1, r = 1e10, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, l = mid + 1;
        else r = mid - 1; 
    } cout << ans << "\n";
    return 0;
}