题面翻译

题目描述

在宇宙一个不为人知的地方，有一个星球，上面有一个国家，只有数学家居住。 在这个国家有$n$个数学家，有趣的是，每个数学家都住在自己的城市，且城市间无道路相连，因为他们可以在线交流。当然，城市有从$1$到$n$的编号。

一位数学家决定用手机发论文，而手机将“不言而喻”自动更正成了“猜谜游戏”。 不久之后，这个国家就发现了猜谜游戏。他们想要见面一起玩，于是这个国家就开始了修路工程。 道路修建会持续$m$天。对于第$i$天，若$\gcd(a,b)=m-i+1$，则$a$和$b$城市间会修一条路。

由于数学家们忙于建筑工作，请你来确定一对数学家最早什么时候能凑到一起玩。

输入输出格式

输入格式

第一行有三个正整数$n,m,q$，表示城市数量、修路持续天数、询问数量。 接下来$q$行，每行有两个正整数$a,b$，表示询问$a$和$b$两个城市的数学家最早什么时候能在一起玩。

输出格式

输出$q$行，第$i$行有一个正整数，表示第$i$次询问的结果

说明

数据范围：
对于$40\%$的数据： $n≤4000,q≤10^5$
对于全部数据：
$1≤n,q≤10^5$
$1≤m≤n$

样例1解释： 在第一天，$(3,6)$之间修了一条路，因此第二次询问输出1
在第二天，$(2,4),(2,6),(2,8),(4,6),(6,8)$之间都修了一条路，此时$4$和$8$号城市连通，第三次询问输出2
在第三天，所有编号互质的城市之间都修了路，$2$和$5$号城市在此时连通，第一次询问输出1

样例2解释： 在第二天，$(20,15)$之间修了一条路
第四天，$(15,9)$之间修了一条路
所以$20$和$9$号城市在第四天连通，输出4

题目描述

There is a planet, in a yet undiscovered part of the universe, with a country inhabited solely by mathematicians. In this country, there are a total of ​N mathematicians, and the interesting fact is that each mathematician lives in their own city. Is it also interesting that no two cities are connected with a road, because mathematicians can communicate online or by reviewing academic papers. Naturally, the cities are labeled with numbers from 1 to ​N.

Life was perfect until one mathematician decided to write an academic paper on their smartphone. The smartphone auto-corrected the word “self-evident” to “Pictionary” and the paper was published as such. Soon after, the entire country discovered pictionary and wanted to meet up and play, so construction work on roads between cities began shortly. . The road construction will last a total of ​M days, according to the following schedule: on the first day, construction is done on roads between all pairs of cities that have ​M as their greatest common divisor. On the second day, construction is done on roads between all pairs of cities that have ​M-1 as their greatest common divisor, and so on until the ​$M^{th}$ day when construction is done on roads between all pairs of cities that are co-prime. More formally, on the $i^{th}$ day, construction is done on roads between cities ​a and ​b if ​gcd(a, b) = $M-i+1$.

Since the mathematicians are busy with construction work, they’ve asked you to help them determine the minimal number of days before a given pair of mathematicians can play pictionary together.

输入格式

The first line of input contains three positive integers ​N, M and ​Q (1 ≤ ​N , ​Q ≤ 100 000, 1 ≤ ​M ≤ ​N ), the number of cities, the number of days it takes to build the roads, and the number of queries.

Each of the following ​Q lines contains two distinct positive integers ​A and ​B (1 ≤ ​A , ​B ≤ ​N ) that denote the cities of the mathematicians who want to find out the minimal number of days before they can play pictionary together.

输出格式

The $i^{th}$ line must contain the minimal number of days before the mathematicians from the $i^{th}$ query can play pictionary together.

样例 #1

样例输入 #1

8 3 3
2 5
3 6
4 8

样例输出 #1

3
1
2

样例 #2

样例输入 #2

25 6 1
20 9

样例输出 #2

4

样例 #3

样例输入 #3

9999 2222 2
1025 2405
3154 8949

样例输出 #3

1980
2160

提示

In test cases worth 40% of total points, it will hold ​N ≤ 1000, ​Q ≤ 100 000.

Clarification of the first test case:

第一天，道路（3、6）建成。 因此，第二个查询的答案是 1。

第二天，道路(2, 4), (2, 6), (2, 8), (4, 6)和(6, 8)被修了。 现在是 4 号和 8 号城市 已连接（可以使用城市 6 从第一个到第二个）。

第三天，相对黄金城市之间的道路已经建成，因此将2号和5号城市连接起来。

Clarification of the second test case:

第二天修路（20、15），第四天修路（15、9）。 之后 第四天，20号和9号城市通过15号城市相连。