[jzoj5782]【NOIP提高A组模拟2018.8.8】城市猎人(并查集按秩合并+复杂度分析)

传送门

Description

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

Input

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

Output

输出q行&＃xff0c;每行一个正整数&＃xff0c;表示最早连通的天数

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%的数据&＃xff0c;n≤ 1000&＃xff0c;q<&＃61;100000
对于100%的数据&＃xff0c;1 ≤ n,q≤ 100000,1<&＃61;m<&＃61;q

Solution

可以发现每一天连的边一定是\(m-i&＃43;1\)的倍数且不小于n&＃xff0c;那么有个结论就是这些边的总数约为\(nlogn\)所以我们可以暴力连边&＃xff0c;边权为天数
那么查询的就是两个点到lca路径上的最大边权&＃xff0c;考虑按秩合并的并查集&＃xff0c;我们知道这个并查集树的深度最大为\(logn\)&＃xff0c;所以每次暴力走到lca并找出答案即可

Code

//By Menteur_Hxy
#include
#include
#include
#include
#include
#include
#define M(a,b) memset(a,(b),sizeof(a))
#define F(i,a,b) for(register int i&＃61;(a);i<&＃61;(b);i&＃43;&＃43;)
#define R(i,a,b) for(register int i&＃61;(b);i>&＃61;(a);i--)
#define E(i,u) for(register int i&＃61;head[u];i;i&＃61;nxt[i])
using namespace std;int read() {int x&＃61;0,f&＃61;1; char c&＃61;getchar();while(!isdigit(c)) {if(c&＃61;&＃61;&＃39;-&＃39;)f&＃61;-f; c&＃61;getchar();}while(isdigit(c)) x&＃61;(x<<1)&＃43;(x<<3)&＃43;c-48,c&＃61;getchar();return x*f;
}const int N&＃61;100010;
int n,m,q;
int fa[N],dis[N],siz[N],dep[N];int getf(int x) {if(fa[x]&＃61;&＃61;x) return dep[x]&＃61;0,x;int father&＃61;getf(fa[x]);dep[x]&＃61;dep[fa[x]]&＃43;1;return father;
}void add(int u,int v,int c) {int fu&＃61;getf(u),fv&＃61;getf(v);if(fu!&＃61;fv) {if(siz[fu]>siz[fv]) swap(fu,fv);fa[fu]&＃61;fv; siz[fv]&＃61;max(siz[fv],siz[fu]&＃43;1);dis[fu]&＃61;c;}
}int main() {freopen("pictionary.in","r",stdin);freopen("pictionary.out","w",stdout);n&＃61;read(),m&＃61;read(),q&＃61;read();F(i,1,n) fa[i]&＃61;i,siz[i]&＃61;1;F(i,1,m) {int x&＃61;m-i&＃43;1;for(register int j&＃61;1;x*j&＃43;x<&＃61;n;j&＃43;&＃43;) add(x*j,x*j&＃43;x,i);}F(i,1,q) {int x&＃61;read(),y&＃61;read(),ans&＃61;0;getf(x);getf(y);if(dep[x]dep[y]) ans&＃61;max(ans,dis[x]),x&＃61;fa[x];while(x!&＃61;y) {ans&＃61;max(ans,dis[x]),x&＃61;fa[x];ans&＃61;max(ans,dis[y]),y&＃61;fa[y];}printf("%d\n",ans);}return 0;
}