题解：P13016 [GESP202506 六级] 最大因数

前言

GESP 6 级真的好水啊，场上一个小时就出来了。

~~比 5 级简单。~~

upd on 2025.8.21，发现一个错误，更正。

题目思路

lca 最近公共祖先问题~~暴力即可通过的~~削弱版。

两个点在树上的距离，可以看作两个点到它们的最近公共祖先的距离之和。观察到数据范围小，每个节点的父节点的值最多是这个节点的

\frac{1}{2}

，所以可以直接暴力模拟往上跳的过程，统计跳的次数之和，即为答案。

给出两个点

l

和

r

，他们的父节点分别为

fl

和

fr

，跳的过程如下：

当 $l < r$ 时， $l = fl$ 。
当 $l > r$ 时， $r = fr$ 。
当 $l = r$ 时，说明已经跳好，返回答案即可。

这样可以有效地求出最近公共祖先。

另外求父节点时运用了类似质数筛的思想，因为往后就重复了，所以枚举最小因数只需从

2

枚举到

\sqrt n

即可。注意判断为质数的情况，直接跳到根节点即可。

code

CPP

#include <bits/stdc++.h>
using namespace std;
int jump(int x)
{
	for (int i = 2; i <= sqrt(x); i++)
		if (x % i == 0)
			return x / i;
	return 1;
}
int lca(int l, int r)
{
	int cnt = 0;
	while (l != r)
	{
		if (l < r)
			r = jump(r);
		else
			l = jump(l);
		cnt++;
	}
	return cnt;
}
void solve()
{
	int q;
	cin >> q; 
	while (q--)
	{
		int l, r;
		cin >> l >> r;
		cout << lca(l, r) << "\n";
	}
}
int main()
{
	solve();
	return 0;
}

题解：P13016 [GESP202506 六级] 最大因数

文章操作

前言

题目思路

code

相关推荐

评论

题解：P13016 [GESP202506 六级] 最大因数