QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46827#3241. 最小公倍树UfowoqqqoTL 773ms36220kbC++1.3kb2022-09-01 23:34:112022-09-01 23:34:12

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-01 23:34:12]
  • 评测
  • 测评结果:TL
  • 用时:773ms
  • 内存:36220kb
  • [2022-09-01 23:34:11]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int N = 1000010;

long long gcd(long long x, long long y)
{
	return y ? gcd(y, x % y) : x;
}

long long lcm(long long x, long long y)
{
	return x * y / gcd(x, y);
}

vector<pair<long long, pair<int, int>>> edges;

int parent[N];

int find(int x)
{
	return parent[x] == x ? x : parent[x] = find(parent[x]);
}

int main()
{
	long long l, r;
	long long i, j;
	long long x;
	long long ans;
	int cnt;
	
	cin >> l >> r;
	
	for(i = l + 1; i <= r; i ++)
	{
		edges.push_back(make_pair(lcm(l, i), make_pair(l, i)));
		for(j = 1; j * j <= i; j ++)
			if(i % j == 0)
			{
				x = (l / j + 1) * j;
				edges.push_back(make_pair(lcm(x, i), make_pair(x, i)));
				x = (l / (i / j) + 1) * (i / j);
				edges.push_back(make_pair(lcm(x, i), make_pair(x, i)));
			}
	}
	
	for(i = l; i <= r; i ++)
		parent[i] = i;
	
	sort(edges.begin(), edges.end());
	for(i = ans = cnt = 0; i < (signed)edges.size(); i ++)
		if(find(edges[i].second.first) != find(edges[i].second.second))
		{
			ans += edges[i].first;
			parent[find(edges[i].second.first)] = find(edges[i].second.second);
			cnt ++;
			if(cnt == r - l)
				break;
		}
	
	cout << ans << endl;
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 628ms
memory: 36216kb

input:

100000 200000

output:

171167496763057

result:

ok single line: '171167496763057'

Test #2:

score: 0
Accepted
time: 773ms
memory: 36220kb

input:

253276 353266

output:

927665531658996

result:

ok single line: '927665531658996'

Test #3:

score: -100
Time Limit Exceeded

input:

655914 755442

output:


result: