QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#281572 | #3241. 最小公倍树 | wtcc# | AC ✓ | 184ms | 36092kb | C++14 | 854b | 2023-12-10 13:09:34 | 2023-12-10 13:09:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5000009;
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;
}
详细
Test #1:
score: 100
Accepted
time: 166ms
memory: 34488kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 156ms
memory: 33704kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 184ms
memory: 35052kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 174ms
memory: 34640kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 0ms
memory: 7476kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 176ms
memory: 36092kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7696kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 0ms
memory: 7688kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 142ms
memory: 34304kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 141ms
memory: 32340kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 167ms
memory: 34224kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'