QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#283500 | #3241. 最小公倍树 | iorit# | AC ✓ | 339ms | 30456kb | C++14 | 2.5kb | 2023-12-14 18:17:20 | 2023-12-14 18:17:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
namespace IO {
#if ONLINE_JUDGE
#define getc() (IS == IT && (IT = (IS = ibuf) + fread(ibuf, 1, IL, stdin), IS == IT) ? EOF : *IS++)
#else
#define getc() getchar()
#endif
const int IL = 1 << 21, OL = 1 << 21;
int olen = 0;
char ibuf[IL], *IS = ibuf, *IT = ibuf, obuf[OL];
inline int read() {
register char ch = getc(); register int x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
return x * f;
}
inline double readdb() {
register char ch = getc(); register double x = 0, f = 1;
while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getc(); }
while(isdigit(ch)) x = x * 10 + ch - 48, ch = getc();
if(ch == '.') {
register double b = 0.1;
ch = getc();
while(isdigit(ch)) x += (ch - 48) * b, b *= 0.1, ch = getc();
}
return x * f;
}
inline int readstr(char *s) {
register char ch = getc(); register int len = 0;
while(!isalpha(ch)) ch = getc();
while(isalpha(ch)) s[++len] = ch, ch = getc();
return len;
}
inline void flush() { fwrite(obuf, 1, olen, stdout); olen = 0; }
inline void putc(register char ch) { obuf[olen++] = ch; }
template<class T>
inline void write(register T x) {
if(x < 0) obuf[olen++] = '-', x = -x;
if(x > 9) write(x / 10);
obuf[olen++] = x % 10 + 48;
}
} using namespace IO;
const int N = 1e6 + 10;
int n, l, r;
struct edge {
int u, v;
ll w;
} e[N * 10];
int cnt;
int fa[N];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool cmp(edge x, edge y) {
return x.w < y.w;
}
ll lcm(int x, int y) {
return 1ll * x * y / __gcd(x, y);
}
int main() {
l = read(), r = read();
if(l == r) {
puts("0");
return 0;
}
n = r - l + 1;
for(int i = l; i <= r; i++) {
for(int j = 1; j * j <= i; j++)
if(i % j == 0) {
int x = l / j;
while(x * j < l || x * j == i) x++;
// cout << x * j << " " << i << endl;
if(x * j <= r) e[++cnt] = {x * j, i, lcm(x * j, i)};
int t = i / j;
if(t == j) continue;
x = l / t;
while(x * t < l || x * t == i) x++;
if(x * t <= r) e[++cnt] = {x * t, i, lcm(x * t, i)};
}
}
sort(e + 1, e + 1 + cnt, cmp);
for(int i = l; i <= r; i++)
fa[i] = i;
ll ans = 0;
for(int i = 1; i <= cnt; i++) {
int x = find(e[i].u), y = find(e[i].v);
if(x == y) continue;
fa[x] = y;
ans += e[i].w;
}
printf("%lld\n", ans);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 229ms
memory: 28608kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 262ms
memory: 28536kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 312ms
memory: 27392kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 339ms
memory: 30456kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 2ms
memory: 7688kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 232ms
memory: 28972kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 1ms
memory: 7732kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 2ms
memory: 7904kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 167ms
memory: 25696kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 125ms
memory: 26820kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 332ms
memory: 30256kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'