A26917. 最大因数
填空题
困难
知识点
题目描述
最大因数
题目描述
给定一棵有 109个结点的有根树，这些结点依次以 1,2,.…,109编号，根结点的编号为1。对于编号为k(2≤k≤109)的结点，其父结点的编号为k的因数中除k以外最大的因数。
现在有 q组询问，第i(1≤i≤q)组询问给定xi,yi，请你求出编号分别为xi,yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
输入格式
第一行，一个正整数 q，表示询问组数。
接下来q行，每行两个正整数xi,yi，表示询问结点的编号。
输出格式
输出共q行，每行一个整数，表示结点xi,yi之间的距离。
样例
输入样例 1
3
1 3
2 5
4 8输出样例 1
1
2
1输入样例 2
1
120 650输出样例 2
9数据范围
对于 60% 的测试点，保证 1 ≤xi,yi≤ 1000。
对于所有测试点，保证1≤q≤1000，1≤xi,yi≤ 109。
参考答案
# 读取询问的组数
n = int(input())
def factorize(x):
"""
得到x以及其全部祖先节点的编号列表，从大到小排列，第一个是x，最后一个是根节点
:param x: 输入节点的编号
:return 一个列表，如上所述
"""
f = [x]
# 遍历能够整除x的最小的数，除掉这个数之后剩下的数就是x最大的因数了
for i in range(2, int(x ** 0.5) + 1):
# 不断除以这个数，直到不能除尽
while x % i == 0:
x //= i
f.append(f[-1] // i)
if f[-1] != 1:
f.append(1)
return f
for _ in range(n):
# 接受这一组输入的x, y
x, y = map(int, input().split())
a = factorize(x)
b = factorize(y)
p1, p2 = 0, 0
# 找到x和y到根节点的路径上最大的公共节点
while a[p1] != b[p2]:
if a[p1] > b[p2]:
p1 += 1
else:
p2 += 1
print(p1 + p2)
上一题
下一题