QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#283500#3241. 最小公倍树iorit#AC ✓339ms30456kbC++142.5kb2023-12-14 18:17:202023-12-14 18:17:21

Judging History

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

  • [2023-12-14 18:17:21]
  • 评测
  • 测评结果:AC
  • 用时:339ms
  • 内存:30456kb
  • [2023-12-14 18:17:20]
  • 提交

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

Details

Tip: Click on the bar to expand more detailed information

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'