QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#282319 | #3241. 最小公倍树 | kilo_tobo_tarjen# | AC ✓ | 99ms | 54076kb | C++20 | 1013b | 2023-12-11 18:56:00 | 2023-12-11 18:56:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const char el = '\n';
typedef long long ll;
const ll inf = 1e18;
ll first(ll l, ll i, ll r, ll d) {
l += (d - l % d) % d;
if (l <= r && l != i) return l * i / d;
return inf;
}
struct edge {
ll u, v;
ll w;
};
struct dsu {
vector<int> f;
dsu(int n) : f(n + 1, -1) {}
int ff(int u) { return ~f[u] ? f[u] = ff(f[u]) : u; }
void conn(int u, int v) {
u = ff(u), v = ff(v);
if (u != v) f[u] = v;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(15);
ll l, r;
cin >> l >> r;
ll ans = 0;
vector<edge> a;
for (int i = 1; i <= r; i++) {
ll s = l + (i - l % i) % i;
for (ll t = s + i; t <= r; t += i) a.push_back({s, t, s * t / i});
}
sort(a.begin(), a.end(), [](edge a, edge b) { return a.w < b.w; });
dsu d(r);
for (auto [u, v, w] : a)
if (d.ff(u) != d.ff(v)) {
ans += w;
d.conn(u, v);
}
cout << ans << el;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 84ms
memory: 54044kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 80ms
memory: 53816kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 76ms
memory: 53260kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 80ms
memory: 53064kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3588kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 85ms
memory: 53212kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3624kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 2ms
memory: 5596kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 84ms
memory: 54076kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 99ms
memory: 52728kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 72ms
memory: 53092kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'