← 返回题目
题库练习 最大因数
← 上一题 下一题 →

A67436 | 最大因数

来源2025年
时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

试题名称：最大因数

时间限制：1.0 s

内存限制：512.0 MB

3.2.1 题目描述

给定一棵有 109个结点的有根树，这些结点依次以1,2,....109 编号，根结点的编号为 1。对于编号为 k（2<=k<=109）的结点，其父结点的编号为 k的因数中除 k以外最大的因数。

现在有 q组询问，第 i（1<=i<=q ）组询问给定xi,yi ，请你求出编号分别为 xi,yi 的两个结点在这棵树上的距离。

两个结点之间的距离是连接这两个结点的简单路径所包含的边数。

3.2.2 输入格式

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

接下来 q行，每行两个正整数 xi,yi ，表示询问结点的编号。

3.2.3 输出格式

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

3.2.4 样例

3.2.4.1 输入样例 1

3

1 3

2 5

4 8

3.2.4.2 输出样例 1

1

2

1

3.2.4.3 输入样例 2

1 

120

650

3.2.4.4 输出样例 2

9

3.2.5 数据范围

C++ 编辑器
输入
输出