g6-02688. GESP-6级-2025-06-最大因数

题目描述

给定一棵有 $1 0^{9}$ 个结点的有根树，这些结点依次以 $1, 2, \dots, 1 0^{9}$ 编号，根结点的编号为 $1$ 。对于编号为 $k$ （ $2 \leq k \leq 1 0^{9}$ ）的结点，其父结点的编号为 $k$ 的因数中除 $k$ 以外最大的因数。

现在有 $q$ 组询问，第 $i$ （ $1 \leq i \leq q$ ）组询问给定 $x_{i}, y_{i}$ ，请你求出编号分别为 $x_{i}, y_{i}$ 的两个结点在这棵树上的距离。两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

第一行，一个正整数 $q$ ，表示询问组数。

接下来 $q$ 行，每行两个正整数 $x_{i}, y_{i}$ ，表示询问结点的编号。

输出共 $q$ 行，每行一个整数，表示结点 $x_{i}, y_{i}$ 之间的距离。

输入

输出

1
2
1

对于 $60%$ 的测试点，保证 $1 \leq x_{i}, y_{i} \leq 1000$ 。

对于所有测试点，保证 $1 \leq q \leq 1000$ ， $1 \leq x_{i}, y_{i} \leq 1 0^{9}$ 。

来源：洛谷 P13016（CCF GESP 六级上机题）