虽然在赛场上不是我写的，但我还是想写题解

本题三种做法：

Kruskal

普遍做法，但是出题人和验题人都没想到。

做法是对于每个数 $d$ ，找到 $p_d$ 为 $d$ 大于等于 $l$ 的最小倍数，将 $d$ 在 $l \sim r$ 的除了 $p_d$ 的其余倍数与 $p_d$ 连边。然后把边排序跑kruskal即可。边数为调和级数，复杂度约为 $O(N log^2 N)$

连通性证明： $d=1$ 时所有数都会和 $l$ 连边，因此一定能构建出最小生成树。

正确性证明（有可能假，看看就好）：对于没选中的一条边 $(x,y)$，设$gcd(x,y)=d$ ,一定能在选中的边中找到两条路径 $(x,p_d)$ 和 $(y,p_d)$ 使得在保证 $x,y$ 连通的前提下最大边权比取 $(x,y)$ 时更小。

upd2022/3/24: 严格证明已经有了，可以看我的这篇题解

代码最好写的一种做法。

代码来源：Qzong

#include<bits/stdc++.h>
const int N=1000010;
int st[N],tot,L,R,tp,l,r;
struct edge{
	int u,v;
	long long w;
}e[N*30];
int p[N];
void init(){
	p[1]=l;
	for(int i=2;i<=r;i++)
		for(int j=i;j<=r;j+=i)
			if(j>=l) {p[i]=j;break;}
	for(int i=r;i>=1;i--)
		for(int j=p[i]+i;j<=r;j+=i)
			e[++tp]=(edge){p[i],j,1ll*p[i]*j/i};
}
bool cmp(edge a,edge b) {return a.w<b.w;}
int f[N];
int find(int x){
	while(x!=f[x])x=f[x]=f[f[x]];
	return x;
}
int main() {
	scanf("%d%d",&l,&r);
	init();
	int cnt=0;
	long long ans=0;
	for(int i=l;i<=r;i++)f[i]=i;
	sort(e+1,e+tp+1,cmp);
	for(int i=1;i<=tp;i++){
		int a=find(e[i].u),b=find(e[i].v);
		if(a==b)continue;
		f[a]=b,cnt++,ans+=e[i].w;
		if(cnt==R-L) break;
	}
	printf("%lld\n",ans);
	return 0;
}

Prim

对于每个因数 $d$ ，用set维护在已选中集合中 $d$ 的倍数的最小值以及在未选中集合中 $d$ 的倍数的最小值 $val_d$。

对所有 $val_d$ 取最小值，使用单次修改 $O(log)$ ，查询 $O(1)$ 的数据结构维护。复杂度对每个 $d$ 维护 $val_d$ 为调和级数级别，数据结构维护为 $O(log)$ 级别，总复杂度 $O(Nlog^2N)$

代码：还没贺到。

Boruvka

u上面应该带个圈，但是我打不出来

鉴于我没学过，且大部分人可能不知道这个算法或者说就我一个不知道
，因此这里贴一下官方题解：

• 一开始每个点属于一个集合。

• 每轮迭代，对每个集合 $S$ 查询 $S$ 与其他集合连边中最小的那条 $e_S$ ，将 $e_S$ 加入最小生成树。

• 如果边权互不相同，保证加入的边不会连成环。

• 查询时枚举每个点 $x$ ，枚举 $x$ 的因数 $d$ ，此时 $x$ 向其他集合连边要么是全局 $d$ 的最小值 $v_d$ ，要么是与 $v_d$ 处于不同集合中的 $d$ 的最小值 $v_d'$ （此时 $x$ 与 $v_d$ 属于同一集合）。

代码来源：NesrayChan

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define ll long long
#define N 1000100
#define pll std::pair<ll,ll>
#define mk std::make_pair
#define oo (1ll<<60)
IL int read()
{
	reg int x=0;reg char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
	return x;
}

int L,R,id[N],buc[N],cnt;
std::vector<int>vec[N],p[N];
std::vector<int>::iterator it,t;

IL int merge(reg int x,reg int y)
{
	if(vec[x].size()<vec[y].size())x^=y^=x^=y;
	for(it=vec[y].begin();it<vec[y].end();++it)id[*it]=x,vec[x].push_back(*it);
	return vec[y].clear(),x;
}

ll ans;
pll f[N],g[N],v;

int main()
{
	L=read(),R=read();
	for(reg int i=L;i<=R;++i)id[i]=i,vec[i].push_back(i);
	for(reg int i=L,d;i<=R;++i)for(d=1;d*d<=i;++d)if(i%d==0)
	{
		p[i].push_back(d);
		if(d*d<i)p[i].push_back(i/d);
	}
	while(cnt<R-L)
	{
		memset(buc+1,0,R<<2);
		for(reg int i=L;i<=R;++i)f[i]=mk(oo,0ll);
		for(reg int i=L;i<=R;++i)if(id[i]==i)
		{
			for(it=vec[i].begin();it<vec[i].end();++it)for(t=p[*it].begin();t<p[*it].end();++t)
				if(buc[*t]&&(v=mk(1ll*buc[*t]*(*it)/(*t),1ll*buc[*t]))<f[*it])f[*it]=v;	
			for(it=vec[i].begin();it<vec[i].end();++it)for(t=p[*it].begin();t<p[*it].end();++t)
				if(!buc[*t]||buc[*t]>*it)buc[*t]=*it;
		}		
		memset(buc+1,0,R<<2);
		for(reg int i=L;i<=R;++i)g[i]=mk(oo,0ll);
		for(reg int i=R;i>=L;--i)if(id[i]==i)
		{
			for(it=vec[i].begin();it<vec[i].end();++it)for(t=p[*it].begin();t<p[*it].end();++t)
				if(buc[*t]&&(v=mk(1ll*buc[*t]*(*it)/(*t),1ll*buc[*t]))<g[*it])g[*it]=v;
			for(it=vec[i].begin();it<vec[i].end();++it)for(t=p[*it].begin();t<p[*it].end();++t)
				if(!buc[*t]||buc[*t]>*it)buc[*t]=*it;
		}	
		for(reg int i=L;i<=R;++i)if(g[i]<f[i])f[i]=g[i];
		for(reg int i=L;i<=R;++i)if(f[i]<f[id[i]])f[id[i]]=f[i];
		for(reg int i=L,j;i<=R;++i)if(id[i]==i&&id[i]!=id[j=f[i].second])
			id[i]=id[j]=merge(id[i],id[j]),++cnt,ans+=f[i].first;
	}
	return printf("%lld",ans),0;
}