$1\le n \le 100000$

Solution：

$n^2$ 暴力加边肯定是不行的，枚举天数 $i$ ，发现所有 $i$ 的倍数的城市都被连了起来，于是不用两两之间连边，直接把 $ki$ 向 $(k+1)i$ 连边即可，带权并查集维护边权，按秩合并，每次暴力查路径上最大值即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m,q;

#define MAXN 100010

int f[MAXN],g[MAXN],siz[MAXN],dep[MAXN];

int find(int x){return (x == f[x] ? x : find(f[x]));}

void merge(int a,int b,int v)

{

	int p = find(a),q = find(b);

	if(p == q)return;

	if(siz[p] > siz[q])swap(p,q);

	f[p] = q;siz[q] += siz[p];g[p] = v;

	return;

}

int getdeep(int x){return (dep[x] == -1 ? (dep[x] = (x == f[x] ? 1 : getdeep(f[x]) + 1)) : dep[x]);}

int query(int a,int b)

{

	if(dep[a] < dep[b])swap(a,b);

	int res = 0;

	while(dep[a] > dep[b])res = max(res,g[a]),a = f[a];

	while(a != b)res = max(res,max(g[a],g[b])),a = f[a],b = f[b];

	return res;

}

int main()

{

	freopen("pictionary.in","r",stdin);

	freopen("pictionary.out","w",stdout);

	scanf("%d%d%d",&n,&m,&q);

	for(int i = 1;i <= n;++i)

		f[i] = i,g[i] = 0,siz[i] = 1,dep[i] = -1;

	for(int i = 1;i <= m;++i)

		for(int k = m - i + 1,j = k;j + k <= n;j += k)merge(j,j + k,i);

	for(int i = 1;i <= n;++i)getdeep(i);

	int a,b;

	for(int i = 1;i <= q;++i)

	{

		scanf("%d%d",&a,&b);

		printf("%d\n",query(a,b));

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}