昨天考 GESP 六级，目前洛谷并没有搬题目，因为官网没有公布。

T2 是这样的：

有一个 $10^9$ 个节点的有根树，且满足：根节点的编号为 $1$，编号为 $k (2≤k≤10^9)$ 的节点的父节点编号为 $k$ 所有因数中除 $k$ 以外最大的一个。给出 $x,y$，求出编号为 $x$ 的节点与编号为 $y$ 的节点的距离。$q$ 组数据，$1≤q≤1000,1≤x,y≤10^9$。

DeepSeek 给出的答案用了最近公共祖先（LCA），这是超出六级考纲范围的。

我有一种思路，因为构造这个树可以发现规律：定义 $p_i$ 表示第 $i$ 个质数，比如 $p_1=2,p_2=3,p_3=5$。编号为 $k$ 的节点的所有子节点中第 $j$ 大的节点编号为 $k\times p_j$。然后打一个质数筛，分别计算编号为 $x$ 的节点与编号为 $y$ 的节点到根节点的距离（类似搜索的方式，不过是一直向上），和编号为 $x$ 的节点与编号为 $y$ 的节点到根节点在上升路径中第一个相遇的点的编号，记作 $z$，计算编号为 $z$ 的节点与根节点的距离。然后会求出三个值 $a,b,c$，输出 $a+b-2c$。样例是通过的，但是提交 WA。

求做法。

输入 1：

3
1 3 1
2 5 2
4 8 1

输出 1：

1
2
1

第 2 个样例忘记了。