QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#281569 | #3241. 最小公倍树 | wtcc# | RE | 0ms | 0kb | C++14 | 854b | 2023-12-10 13:07:14 | 2023-12-10 13:07:15 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1000009;
ll a[N],L,R,p[N],m;
struct edge{
ll u,v,w;
}edges[N];
ll fl(ll x){
if(p[x]==x) return x;
else return p[x]=fl(p[x]);
}
bool cmp(edge x,edge y){
return x.w<y.w||x.w==y.w&&x.u<y.u;
}
int main(){
cin>>L>>R;
for(ll i=L;i<=R;i++) p[i]=i;
for(ll i=1;i<=R;i++){
ll f=ceil(1.0*L/i)*i;
for(ll j=f+i;j<=R;j+=i){
// cout<<f<<" "<<j<<endl;
edges[++m]=(edge){f,j,f*j/__gcd(f,j)};
}
}
ll ans=0,chosen=0;
sort(edges+1,edges+1+m,cmp);
for(ll i=1;i<=m;i++){
ll u=edges[i].u,v=edges[i].v,w=edges[i].w;
if(fl(u)==fl(v)) continue;
chosen++;
// cout<<u<<" "<<v<<" "<<w<<endl;
p[fl(u)]=fl(v);
ans+=w;
if(chosen==R-L) break;
}
cout<<ans<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
100000 200000