QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#46826#3241. 最小公倍树UfowoqqqoTL 0ms0kbC++1.3kb2022-09-01 23:33:502022-09-01 23:33:53

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:33:53]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2022-09-01 23:33:50]
  • 提交

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;
	
	freopen("t.in", "r", stdin);
	
	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;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

100000 200000

output:


result: