QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#240411#3241. 最小公倍树Cofe_Milk#AC ✓140ms35632kbC++171.0kb2023-11-05 15:16:292023-11-05 15:16:30

Judging History

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

  • [2023-11-05 15:16:30]
  • 评测
  • 测评结果:AC
  • 用时:140ms
  • 内存:35632kb
  • [2023-11-05 15:16:29]
  • 提交

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

详细

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'