QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#563131#3241. 最小公倍树ElegiaAC ✓166ms36180kbC++231.2kb2024-09-14 03:00:202024-09-14 03:00:20

Judging History

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

  • [2024-09-14 03:00:20]
  • 评测
  • 测评结果:AC
  • 用时:166ms
  • 内存:36180kb
  • [2024-09-14 03:00:20]
  • 提交

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'