题目描述：
有 (n) 个城市，标号为 (1) 到 (n)，第 (i) 天时，若 (gcd(a,b)=m-i+1)，则标号为 (a) 的城 市和标号为 (b) 的城市会建好一条直接相连的道路，有多次询问，每次询问某两座 城市最早什么时候能联通。
大体思路：
首先解决建边问题，我们不可能去枚举每一对点，然后判断它们是否联通。
对于询问，其实我们只要找出它的一颗最小生成树即可。
所以我们枚举(gcd)，对于每一个(gcd)，我们只需要考虑(gcd)与它的倍数之间的连边即可。
考虑并查集，如果这两个点不在同一个并查集中便连边。
之后可以用树上倍增解决，但是我为了追求理论时间复杂度，就用了(LCT)。
然鹅，被(O(n log^2 n))的树上倍增吊打。。。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int w[N],val[N],ch[N][2],fa[N],rev[N],f[N];
int n,m,q,x,y,tot;
int gcd(int a,int b){return a%b==0?b:gcd(b,a%b);}
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}
bool wh(int x){return ch[fa[x]][1]==x;}
bool isrt(int x){return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
void rever(int x){rev[x]^=1,swap(ch[x][0],ch[x][1]);}
void update(int x){val[x]=max(max(val[ch[x][0]],val[ch[x][1]]),w[x]);}
void pushdown(int x){
if (rev[x]){
if (ch[x][0]) rever(ch[x][0]);
if (ch[x][1]) rever(ch[x][1]);
rev[x]=0;
}
}
void Allpushdown(int x){
if (!isrt(x)) Allpushdown(fa[x]);
pushdown(x);
}
void rotate(int x){
int y=fa[x],z=fa[y],c=wh(x);
if (!isrt(y)) ch[z][wh(fa[x])]=x;
fa[x]=z;
ch[y][c]=ch[x][c^1];
fa[ch[y][c]]=y;
ch[x][c^1]=y;
fa[y]=x;
update(y),update(x);
}
void splay(int x){
Allpushdown(x);
for (;!isrt(x);rotate(x))
if (!isrt(fa[x])) rotate(wh(x)==wh(fa[x])?fa[x]:x);
}
void access(int x){
for (int y=0;x;y=x,x=fa[x]) splay(x),ch[x][1]=y,update(x);
}
void makert(int x){
access(x),splay(x),rever(x);
}
void link(int x,int y){
makert(x),fa[x]=y;
}
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;
for (int i=m;i>=1;i--){
if (tot==n-1) break;
for (int j=1;j*i<=n;j++){
if (tot==n-1) break;
int f1=find(i),f2=find(i*j);
if (f1!=f2){
++tot;
w[tot+n]=m-i+1;
f[f1]=f2;
link(i*j,tot+n),link(i,tot+n);
if (tot==n-1) break;
}
}
}
for (int i=1;i<=q;i++){
scanf("%d%d",&x,&y);
makert(x),access(y),splay(y);
printf("%d
",val[y]);
}
return 0;
}