luogu P8207 题解

在暴力建边的情况下可以 kruskal 求生成树。

但是这样是 \(O(n^2)\) 的。

因为 \(lcm(x,y) = x \times y / \gcd(x,y)\)。

所以 \(\gcd(x,y)\) 越大我们的答案越优。

但是枚举 \(x\) 和 \(y\) 求 \(\gcd(x,y)\) 也是会超时的。

但是我们用 正难则反 的思想，对于每一个 \(i \in[L,R]\) 枚举倍数。

而 \(i\) 是这些数的最大公因数的因数。

而这样做是 \(\sum_{i=1}^{i=n} n/i = \log n\) 的。

因此总复杂度是 \(O(n \log^2 n)\) 的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn =4e6+100;
int tot;
struct node{
    int u,v,w;
}edge[maxn];
bool cmp(node a,node b){
    return a.w<b.w;
}
int fa[maxn];
int found(int u){
    if(fa[u]==u){
        return u;
    }
    else{
        return fa[u]=found(fa[u]);
    }
}
int res=0;   hg
signed main(){
    int l,r;
    cin>>l>>r;
    for(int i=l;i<=r;i++) fa[i]=i;
    for(int i=1;i<=r;i++){
        int v=ceil(l*1.0/i)*i;
        for(int j=ceil(l*1.0/i)*i;j<=r;j+=i){
            if(v!=j){
                edge[++tot].u=v;
                edge[tot].v=j;
                edge[tot].w=v*j/__gcd(v,j);
            }
        }
    }
    sort(edge+1,edge+tot+1,cmp);
    for(int i=1;i<=tot;i++){
        int u=edge[i].u;
        int v=edge[i].v;
        int w=edge[i].w;
        if(found(u)!=found(v)){
            //cout<<u<<' '<<v<<' '<<w<<'\n';
            fa[found(u)]=found(v);
            res+=w;
        }
    }
    cout<<res;
}