题目 题解 –本来是很难，但是总有优秀的大佬加神牛犇活在这个世界上 首先不用n^2枚举a和b， 某位大佬说： a和b其实就是 1 * （m-i+1），2 * （m-i+1），3 * （m-i+1），4 * （m-i+1）。。。。 （哇，我咋不知道呢QAQ） 那么用并查集建一棵树就好了 树边就是连接他们的 i 然后好像有什么优化？——小树连大树（按秩合并） 最后跑对于每

有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。 对于40%的数据，n≤ 1000，q<=100000 对于100%的数据，1 ≤ n,q≤ 100000,1<=m<=q 如果想到了kruskal重构树，那应该是学傻了 像我一样 直接并查集按秩合并

Description 有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。   Input 第一行输入三个正整数n,m,q，其中q表示询问个数。 接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。   Outpu