QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#46827 | #3241. 最小公倍树 | Ufowoqqqo | TL | 773ms | 36220kb | C++ | 1.3kb | 2022-09-01 23:34:11 | 2022-09-01 23:34:12 |
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;
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