QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#281572#3241. 最小公倍树wtcc#AC ✓184ms36092kbC++14854b2023-12-10 13:09:342023-12-10 13:09:34

Judging History

你现在查看的是最新测评结果

  • [2023-12-10 13:09:34]
  • 评测
  • 测评结果:AC
  • 用时:184ms
  • 内存:36092kb
  • [2023-12-10 13:09:34]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'