QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#240411 | #3241. 最小公倍树 | Cofe_Milk# | AC ✓ | 140ms | 35632kb | C++17 | 1.0kb | 2023-11-05 15:16:29 | 2023-11-05 15:16:30 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
//#define int ll
#define endl '\n'
#define fi first
#define se second
#define pii pair<int, int>
#define rep(i,a,n,k) for(int i=a;i<=n;i+=k)
#define per(i,a,n,k) for(int i=a;i>=n;i-=k)
/*·········································*/
const int N = 2e7 + 10;
int l, r;
int f[N], tot;
ll ans;
array<ll, 3> ay[N];
int find(int k)
{
return f[k] == k ? k : f[k] = find(f[k]);
}
void solve()
{
cin >> l >> r;
rep(i,l,r,1) f[i] = i;
rep(i,1,1e5,1)
{
ll x = 0;
rep(j,i,r,i) if(j >= l && j <= r)
{
if(!x) x = j;
else ay[++ tot] = {x / i * j, x, j};
}
}
sort(ay + 1, ay + 1 + tot);
rep(i,1,tot,1)
{
int a = find(ay[i][1]), b = find(ay[i][2]);
if(a != b)
{
ans += ay[i][0];
f[a] = b;
}
}
cout << ans;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
int t = 1;
//cin>>t;
while(t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 118ms
memory: 33256kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 115ms
memory: 31856kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 108ms
memory: 31552kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 113ms
memory: 35632kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5600kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 112ms
memory: 31796kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 2ms
memory: 5700kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 3ms
memory: 5612kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 140ms
memory: 34208kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 132ms
memory: 30576kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 121ms
memory: 35192kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'