模考T2桥对着回放错的代码WA0样例输出5 5 5

常规
1
  1. 桥
    题目ID：19606必做题文件操作100分

订正得分

赛中得分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 2000ms
空间限制: 262144kB
输入文件名: data.in
输出文件名: data.out
题目描述
有
n
n 座海上城市，一开始每座海上城市之间都没有连接。现在大统治者计划在这些城市之间修建浮桥，她制定修建日期为
m
m 天，由于一开始一些城市之间不具备修建浮桥的条件，他施展了永续法术以降低海平面高度，因此在第
i
i 天时，如果城市
a
a 和城市
b
b 满足
g
c
d
(
a
,
b
)

m
−
i
+
1
gcd(a,b)=m−i+1，这两个城市之间就会修建浮桥，并且浮桥可以持续使用。

现在给出
q
q 个询问，询问
a
b
ab 之间最早能在第几天联通。

输入格式
第一行三个正整数
1
≤
n
,
m
,
q
≤
1
0
5
1≤n,m,q≤10
5
，表示城市数，修建天数和询问数。

接下来
q
q 行每行两个整数
1
≤
a
,
b
≤
n
1≤a,b≤n，询问城市
a
a 城市
b
b 最早几天内联通。

输出格式
一共
q
q 行，每行一个正整数表示各个询问的答案

样例
Input 1
8 3 3
2 5
3 6
4 8
Output 1
3
1
2
样例解释
显然
a

b
a=b时，城市在第
0
0天就已经联通。
第一天会连通
g
c
d
(
a
,
b
)

3
gcd(a,b)=3的城市，也就是
(
3
,
6
)
(3,6)

第二天会连通
g
c
d
(
a
,
b
)

2
gcd(a,b)=2的城市，也就是
(
2
,
4
)
,
(
2
,
6
)
,
(
4
,
6
)
,
(
2
,
8
)
,
(
6
,
8
)
(2,4),(2,6),(4,6),(2,8),(6,8)

第三天会连通
g
c
d
(
a
,
b
)

1
gcd(a,b)=1的城市，也就是
(
1
,
2
)
,
(
1
,
3
)
,
(
1
,
4
)
,
(
1
,
5
)
,
(
2
,
3
)
,
(
2
,
5
)
,
(
3
,
4
)
,
(
3
,
5
)
,
(
4
,
5
)
(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5),(4,5)

对于
2
,
5
2,5，会在第
3
3天联通，对于
3
,
6
3,6，会在第
1
1天联通，对于
4
,
8
4,8，会在第二天存在路径
4
→
6
→
8
4→6→8联通。

数据范围
对于
20
%
20% 的数据满足：
1
≤
n
,
m
≤
10
1≤n,m≤10

对于
60
%
60% 的数据满足：
1
≤
n
,
m
≤
2000
1≤n,m≤2000

对于
100
%
100% 的数据满足：
1
≤
n
,
m
≤
1
0
5
1≤n,m≤10
5

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,q;
int a,b;
int ans[N];
int fa[N];
set<int> st[N];
int find(int x){
	if(fa[x]==x){
		return x;
	}
	return fa[x]=find(fa[x]);
}
void find_(int u,int v,int id){
	u=find(u);
	v=find(v);
	if(u==v){
		return;
	}
	if(st[u].size()>st[v].size()){
		swap(u,v);
	}
	for(auto &i:st[u]){
		if(st[v].count(i)!=0){
			ans[i]=id;
		}
		else{
			st[v].insert(i);
		}
	}
	fa[u]=v;
}

signed main(){
	freopen("data.in","r",stdin);
	freopen("data.out","w",stdout);
	cin>>n>>m>>q;
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1;i<=n;i++){
		fa[i]=i;
	}
	for(int i=1;i<=q;i++){
		scanf("%lld%lld",&a,&b);
		if(a==b){//直接就自己跟自己了是吧 
			ans[i]=0;
			continue;
		}
		st[a].insert(i);
		st[b].insert(i);
		ans[i]=m;
	}
	for(int i=m;i>=2;i--){//按天走 
		for(int j=i*2;j<=n;j+=i){
			find_(i,j,m+1-i);
		}
	}
	for(int i=1;i<=q;i++){
		printf("%lld\n",ans[i]);
	}
	return 0;
}
/*


*/