#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
using namespace std;
typedef long long ll;
const int N = 200100;
vector<int> qr[N];
int pr[N], n, m, q, x[N], y[N], L[N], R[N], mid[N];
int get(int x) { return (pr[x] == x ? x : pr[x] = get(pr[x])); }
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef _LOCAL
freopen("in.txt","r",stdin);
#endif // _LOCAL
cin >> n >> m >> q;
for (int i = 0; i < q; i++){
cin >> x[i] >> y[i];
L[i] = 1; R[i] = m;
}
bool was = 1;
while (was){
was = 0;
for (int i = 0; i < q; i++)
if (L[i] < R[i]){
mid[i] = (L[i] + R[i] + 1) >> 1;
qr[mid[i]].PB(i);
}
for (int i = 1; i <= n; i++)
pr[i] = i;
for (int i = m; i > 1; i--){
for (int j = i + i; j <= n; j += i)
pr[get(j)] = get(i);
if (sz(qr[i])) {
for (int nm : qr[i])
if (get(x[nm]) == get(y[nm]))
L[i] = mid[i];
else R[i] = mid[i - 1];
qr[i].clear();
}
}
}
for (int i = 0; i < q; i++)
cout << L[i] << "\n";
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
8 ms |
5248 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
13 ms |
5632 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
25 ms |
7040 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
32 ms |
8060 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
22 ms |
6784 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
24 ms |
7040 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
33 ms |
7800 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
40 ms |
8572 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
43 ms |
8948 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
52 ms |
9332 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |