简答题 偏难
#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] &gt; b[p2]:             p1 += 1         else:             p2 += 1     # 输出两段路径步数之和     print(p1 + p2)</pre>
这道题暂未补解析。