← 返回题目

题库练习最大因数

← 上一题下一题 →

A71910 | $最大因数$

来源编程题

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

给定一棵有 10^9 个结点的有根树，这些结点依次以 1，2，...，10^9 编号，根结点的编号为 1。对于编号为 k（2 \le k \le 10^9）的结点，其父结点的编号为 k 的因数中除 k 以外最大的因数。 现在有 q 组询问，第 i（ 1 \le i \le q）组询问给定x_i，y_i ，请你求出编号分别为 x_i，y_i 的两个结点在这棵树上的距离。 两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

输入格式

第一行，一个正整数 q ，表示询问组数。 接下来 q 行，每行两个正整数 x_i，y_i ，表示询问结点的编号。

输出格式

输出共 q 行，每行一个整数 ，表示结点 x_i，y_i 之间的距离。

输入输出样例

输入 #1

输出 #1

1
2
1

输入 #2

1
120 650

输出 #2

C++ 编辑器

输入

输出