[数论][LCA][并查集]JZOJ 5782 城市猎人

Description

有n个城市，标号为1到n，修建道路花费m天，第i天时，若gcd(a,b)=m-i+1，则标号为a的城市和标号为b的城市会建好一条直接相连的道路，有多次询问，每次询问某两座城市最早什么时候能连通。
 

 

Input

第一行输入三个正整数n,m,q，其中q表示询问个数。
接下来q行，每行两个正整数x，y，表示询问城市x和城市y最早什么时候连通。
 

Output

输出q行，每行一个正整数，表示最早连通的天数
 

 

Sample Input

Input 1
8 3 3
2 5
3 6
4 8
Input 2
25 6 1
20 9
Input 3
9999 2222 2
1025 2405
3154 8949
 

Sample Output

Output 1
3
1
2
Output 2
4
Output 3
1980
2160
 

 

Data Constraint

对于40%的数据，n≤ 1000，q<=100000
对于100%的数据，1 ≤ n,q≤ 100000,1<=m<=q

分析

显然对于gcd(a,b)=k，a与b都是k的倍数且a/k+1=b/k

那么我们就知道，第i天会有这样一个数列变得连通：m-i+1,2*(m-i+1),3*(m-i+1),...

那么问题就变成了求问两个连通块之间最早的连通时间

我们想到了并查集，但是不能路径压缩，这样会破坏数据详细性

只能按秩合并咯

然后对于每个点给一个ti表示i这个点与父亲相连通的最早时间

那么我们预处理好并查集，求x,y到它们LCA（不包括LCA，注意！）的max{ti 即可

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=1+1e5;
int n,m,q;
int f[N],r[N],t[N],d[N];

int Get(int x) {
    if (x==f[x]) return x;
    int root=Get(f[x]);
    d[x]=d[f[x]]+1;
    return root;
}

int Ask(int x,int y) {
    int ans=0;
    if (d[x]<d[y]) swap(x,y);
    while (d[x]>d[y]) ans=max(ans,t[x]),x=f[x];
    while (x!=y) {
        ans=max(ans,max(t[x],t[y]));
        x=f[x];y=f[y];
    }
    return ans;
}

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,r[i]=1;
    for (int i=1;i<=m;i++) {
        for (int j=2;j<=n/(m-i+1);j++) {
            int u=Get((m-i+1)*(j-1)),v=Get((m-i+1)*j);
            if (u==v) continue;
            if (r[u]<=r[v]) {
                f[u]=v;t[u]=i;
                r[v]=max(r[u]+1,r[v]);
            }
            else {
                f[v]=u;t[v]=i;
                r[u]=max(r[v]+1,r[u]);
            }
        }
    }
    for (int i=1;i<=n;i++) Get(i);
    for (int i=0;i<q;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        Get(a);Get(b);
        printf("%d\n",Ask(a,b));
    }
    fclose(stdin);fclose(stdout);
}