计算最大因数构造树中两节点的距离
时间限制：1.0 s 内存限制：512.0 MB
题目描述
给定一棵有 $10^9$ 个结点的有根树，结点编号为 $1,2,\dots,10^9$，根结点编号为1。对于编号为 $k$（$2 \leq k \leq 10^9$）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。
现有 $q$ 组询问，每组给定 $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 \leq x_i,y_i \leq 1000$
- 对于所有测试点，保证 $1 \leq q \leq 1000$，$1 \leq x_i,y_i \leq 10^9$
本题为编程题，提交代码并运行通过测试点后判分。
正在加载题目数据…
子题
该题型需在试卷/作业中作答，单题练习暂不支持
答案解析
提交记录
共 条
仅展示自由练习提交
正在加载提交记录…
状态
得分率
提交时间
平均用时
平均内存
使用语言
提交人
加载失败
暂无自由练习提交记录