B

 1 Sec 256 MB |  Markdown 获取标签

 

题目描述

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

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

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

输入格式

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

输出格式

输出 qq 行,第 ii 行有一个正整数,表示第 ii 次询问的结果。

样例输入 #1

8 3 3
2 5
3 6
4 8

样例输出 #1

3
1
2

样例输入 #2

25 6 1
20 9

样例输出 #2

4

样例输入 #3

9999 2222 2
1025 2405
3154 8949

样例输出 #3

1980
2160

提示

1n,q1051≤n,q≤10^5
1mn1≤m≤n

 

 您尚未登录,无法进行代码提交

2024 秋季 个人排位赛(四)

2024-07-13 12:00
2024-07-13 17:00
Ended