CF1285F Classical

Description

给定 $n$ 个数 $a_1,\cdots, a_n$ ，求两两 $\text{lcm}$ 的最大值。
$1\leq n,a_i\leq 10^5$

Solution

nb 题。
考虑枚举 $\gcd=d$ 。将 $d$ 的倍数放在同一个集合内，问题转化为在集合内找一组 $(a,b)$ ，满足 $\gcd(a,b)=d$ ，且 $a\times b$ 最大。

先将集合内的元素都除以 $d$ ，则要求变成 $\gcd(a,b)=1$ 。
我们将元素从大至小排序，并逐个枚举。设当前枚举的是 $x$ 。假如曾经枚举过一个数 $z$ ，满足 $\gcd(x,z)=1$ ，事实上 $z\sim x$ 之间的元素就没有用处了。所以我们可以拿栈来维护，每次判定是否存在 $z$ 使得 $\gcd(x,z)=1$ ，然后不断弹栈。

问题转化为如何快速判定一个集合内有多少个数与当前数互质。设 $c_i$ 表示 $i$ 的出现次数，也就是求：

$\sum_{i\ge 0}c_i[\gcd(i,x)=1]$

莫比乌斯反演一下可以得到

$\sum_{t|x}\mu_t\sum_{i|t}c_i$

所以可以每次加入集合/弹出集合时暴力给因数的 $c_i$ 加/减一，查询时枚举因数求和。

复杂度 $\mathcal{O}(n\log_2^2n)$。每个数均摊入 $\log_2$ 次栈，栈内元素求 $\gcd$ 需要一个 $\log_2n$ 。

Code

const int N = 1e5 + 5;
using namespace std;
int n, m, num;
int a[N], b[N], p[N], s[N], mu[N], cnt[N];
vector<int>d[N];
bitset<N>ok;
void Prework(int n){
    mu[1] = 1;
    for(int i = 2; i <= n; ++i){
        if(!ok[i]) p[++num] = i, mu[i] = -1;
        for(int j = 1; j <= num and p[j] * i <= n; ++j){
            ok[i * p[j]] = 1;
            if(i % p[j] == 0) break;
            mu[i * p[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= n; ++i)
    for(int j = i; j <= n; j += i)
        d[j].push_back(i);
}
int gcd(int x, int y){
    return (!y) ? x : gcd(y, x % y); 
}
int main(){
    
    Prework(1e5);

    r(n);
    for(int i = 1; i <= n; ++i)
        r(a[i]), ++b[a[i]], m = max(a[i], m);
    long long ans = 0;
    vector<int> v;
    for(int i = 1; i <= m; ++i){
        v.clear();
        for(int j = i; j <= m; j += i)
        for(int k = 1; k <= b[j]; ++k)
            v.push_back(j / i);
        int top = 0;
        reverse(v.begin(), v.end());
        for(auto x:v){
            int res = 0;
            for(auto y:d[x]) res += cnt[y] * mu[y];
            while(res){
                int z = s[top];
                if(gcd(z, x) == 1)
                    ans = max(1ll * x * z * i, ans), --res;
                for(auto y:d[z]) --cnt[y];
                --top;
            }
            s[++top] = x;
            for(auto y:d[x]) ++cnt[y];
        }
        while(top) {
            int x = s[top];
            for(auto y:d[x]) --cnt[y]; 
            --top;
        }
    }
    w(ans);
    return 0;
}
复制代码