简答题
偏难
#17472
最大因数
最大因数



答案与解析
正确答案:<pre class="brush:python;toolbar:false;"># 读取询问的组数
n = int(input())
def factorize(x):
"""
得到x以及其全部祖先节点的编号列表,从大到小排列
第一个是x,最后一个是根节点1
:param x: 输入节点的编号
:return: 路径列表
"""
f = [x]
# 寻找质因数分解
for i in range(2, int(x ** 0.5) + 1):
while x % i == 0:
x //= i
f.append(f[-1] // i)
# 末尾补上根节点1
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
# 双指针找第一个相同公共节点
while a[p1] != b[p2]:
if a[p1] > b[p2]:
p1 += 1
else:
p2 += 1
# 输出两段路径步数之和
print(p1 + p2)</pre>
这道题暂未补解析。