题目链接

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define qwq cout<<endl
#define int ll
ll l,r;
struct nidie{
	ll u,v,w;
}e[5000010];
ll fa[100010];
ll tail;
ll find(ll x){
	if(fa[x]==x) return x;
	fa[x]=find(fa[x]);
	return fa[x];
}
bool cmp(nidie x,nidie y){
	return x.w<y.w;
}
ll gcd(ll x,ll y){
	return !y ? x : gcd(y,x%y);
}
ll lcm(ll x,ll y){
	return x*y/gcd(x,y);
}
ll ans,q;
bool fg;
signed main(){
	ll i,j; 
	cin>>l>>r;
	for(i=2;i<=r;i++){
		fg=0;
		for(j=i;j<=r;j+=i){
			if(j>=l){
				if(!fg){
					q=j;
					fg=1;
				}
				e[++tail]={q,j,lcm(q,j)};
                //只对这些明显更优的情况连边
			}
		}
		if(i>=l){
			e[++tail]={q,l,lcm(l,q)};
		}
	}
	for(i=l;i<=r;i++){
		fa[i]=i;
	}
	sort(e+1,e+1+tail,cmp);
	for(i=1;i<=tail;i++){
		ll f1=find(e[i].u),f2=find(e[i].v);
		if(f1==f2) continue;
		fa[f1]=f2;
		ans+=e[i].w;
	}
	cout<<ans;
	return 0;
}

不知为何，对于第四个样例，我的输出是0，但是并没有哪里没开longlong

#4输入

325735 425533

#4输出

1483175252352926

我的#4输出

0