QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#563131 | #3241. 最小公倍树 | Elegia | AC ✓ | 166ms | 36180kb | C++23 | 1.2kb | 2024-09-14 03:00:20 | 2024-09-14 03:00:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
int L,R;
int fa[MAXN];
ll ans;
ll val[MAXN];
vector<int> Q[MAXN];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > S;
int getroot(int u)
{
return u == fa[u] ? u : fa[u] = getroot(fa[u]);
}
void work(int u)
{
int tmp = Q[u].back();
Q[u].pop_back();
Q[u].pop_back();
Q[u].push_back(tmp);
if (Q[u].size() > 1)
{
val[u] = (ll)Q[u].back() * Q[u][Q[u].size() - 2] / u;
S.push(make_pair(val[u],u));
}
}
int main()
{
cin >> L >> R;
for (int i = L;i <= R;i++)
fa[i] = i;
for (int i = 1;i <= R;i++)
{
int st = ((L - 1) / i + 1) * i;
for (int j = st;j <= R;j += i)
Q[i].push_back(j);
reverse(Q[i].begin(),Q[i].end());
if (Q[i].size() > 1)
{
val[i] = (ll)Q[i].back() * Q[i][Q[i].size() - 2] / i;
S.push(make_pair(val[i],i));
}
}
while (!S.empty())
{
int u = S.top().second;
S.pop();
if (getroot(Q[u].back()) == getroot(Q[u][Q[u].size() - 2]))
{
work(u);
continue;
}
ans += val[u];
fa[getroot(Q[u].back())] = getroot(Q[u][Q[u].size() - 2]);
work(u);
}
printf("%lld\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 78ms
memory: 24496kb
input:
100000 200000
output:
171167496763057
result:
ok single line: '171167496763057'
Test #2:
score: 0
Accepted
time: 84ms
memory: 27948kb
input:
253276 353266
output:
927665531658996
result:
ok single line: '927665531658996'
Test #3:
score: 0
Accepted
time: 85ms
memory: 34592kb
input:
655914 755442
output:
5580601534791953
result:
ok single line: '5580601534791953'
Test #4:
score: 0
Accepted
time: 79ms
memory: 34412kb
input:
900000 1000000
output:
10250678499914055
result:
ok single line: '10250678499914055'
Test #5:
score: 0
Accepted
time: 2ms
memory: 5844kb
input:
99991 99991
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 87ms
memory: 28176kb
input:
99991 199982
output:
171132525371252
result:
ok single line: '171132525371252'
Test #7:
score: 0
Accepted
time: 0ms
memory: 5780kb
input:
100003 100003
output:
0
result:
ok single line: '0'
Test #8:
score: 0
Accepted
time: 3ms
memory: 8068kb
input:
666666 666667
output:
444444222222
result:
ok single line: '444444222222'
Test #9:
score: 0
Accepted
time: 166ms
memory: 18604kb
input:
1 99667
output:
4966805277
result:
ok single line: '4966805277'
Test #10:
score: 0
Accepted
time: 155ms
memory: 20232kb
input:
2 99248
output:
5373052945
result:
ok single line: '5373052945'
Test #11:
score: 0
Accepted
time: 88ms
memory: 36180kb
input:
798954 898945
output:
8177721171091522
result:
ok single line: '8177721171091522'