最大因数构造树的两结点距离计算
题目描述
给定一棵有10^9个结点的有根树，结点编号依次为1,2,3,…,10^9，根结点编号为1。对于编号为k（2 ≤ k ≤ 10^9）的结点，其父结点编号为k的因数中除k以外最大的因数。
现有q组询问，第i（1 ≤ i ≤ q）组询问给定x_i, y_i，请求出编号为x_i和y_i的两个结点在树上的距离（两个结点之间的距离定义为连接它们的简单路径包含的边数）。
输入格式
第一行一个正整数q，表示询问组数。 接下来q行，每行两个正整数x_i, y_i，表示询问的结点编号。
输出格式
输出共q行，每行一个整数，表示对应询问的两结点距离。
输入样例1
3
1 3
2 5
4 8输出样例1
1
2
1输入样例2
1
120 650输出样例2
9数据范围
- 对于60%的测试点，保证1 ≤ x_i, y_i ≤ 1000
- 对于所有测试点，保证1 ≤ q ≤ 1000，1 ≤ x_i, y_i ≤ 10^9
本题为编程题，提交代码并运行通过测试点后判分。
正在加载题目数据…
子题
该题型需在试卷/作业中作答，单题练习暂不支持
答案解析
提交记录
共 条
仅展示自由练习提交
正在加载提交记录…
状态
得分率
提交时间
平均用时
平均内存
使用语言
提交人
加载失败
暂无自由练习提交记录