QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#46826 | #3241. 最小公倍树 | Ufowoqqqo | TL | 0ms | 0kb | C++ | 1.3kb | 2022-09-01 23:33:50 | 2022-09-01 23:33:53 |
Judging History
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