//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T> ostream& operator<<(ostream& os, const set<T>& v){os << "[";for (auto i = v.begin(); i != v.end();) { os << *i; i++; if (i != v.end()) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold
#define N (100'005)
#define MOD (1'000'000'007ll)
#define OO (1'050'000'000)
#define OOL (1'100'000'000'000'000'000ll)
//global
int ans[N];
struct component{
int par;
int sz;
set<int> numbers;
map<int,vector<int>> requests;
};
component dsu[N];
int home(int u){
if(dsu[u].par == u) return u;
dsu[u].par = home(dsu[u].par);
return dsu[u].par;
}
void merge(int u,int v,int c){
u = home(u); v = home(v);
if(u == v) return;
// cout << u << ": " << dsu[u].requests << "," << dsu[u].numbers << endl;
// cout << v << ": " << dsu[v].requests << "," << dsu[v].numbers << endl;
if(sz(dsu[u].requests) <= sz(dsu[v].numbers)){
vector<int> tbd;
for(auto el:dsu[u].requests){
if(dsu[v].numbers.count(el.first)){
tbd.push_back(el.first);
for(int id:el.second){
ans[id] = c;
}
}
}
for(int el:tbd) dsu[u].requests.erase(el);
}else{
vector<int> tbd;
for(int tar:dsu[v].numbers){
if(dsu[u].requests.count(tar)){
tbd.push_back(tar);
for(int id:dsu[u].requests[tar]){
ans[id] = c;
}
}
}
for(int el:tbd) dsu[u].requests.erase(el);
}
if(sz(dsu[v].requests) <= sz(dsu[u].numbers)){
vector<int> tbd;
for(auto el:dsu[v].requests){
if(dsu[u].numbers.count(el.first)){
tbd.push_back(el.first);
for(int id:el.second){
ans[id] = c;
}
}
}
for(int el:tbd) dsu[v].requests.erase(el);
}else{
vector<int> tbd;
for(int tar:dsu[u].numbers){
if(dsu[v].requests.count(tar)){
tbd.push_back(tar);
for(int id:dsu[v].requests[tar]){
ans[id] = c;
}
}
}
for(int el:tbd) dsu[v].requests.erase(el);
}
if(dsu[u].sz < dsu[v].sz) swap(u,v);
for(int el:dsu[v].numbers) dsu[u].numbers.insert(el);
for(auto el:dsu[v].requests)
dsu[u].requests[el.first].insert(
dsu[u].requests[el.first].end(),
el.second.begin(), el.second.end()
);
dsu[u].sz += dsu[v].sz;
dsu[v].par = u;
// cout << u << "+" << v << ": " << dsu[u].requests << "," << dsu[u].numbers << endl;
// cout << endl;
}
vector<int> coprime[330];
int main(){
//fold
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cout << setprecision(10);
//endfold
int n,m,q;
cin >> n >> m >> q;
for (int i = 0; i < n; ++i){
dsu[i+1] = {i+1,1,{i+1},{}};
}
rep(i,0,q){
int u,v;
cin >> u >> v;
if(u > v) swap(u,v);
dsu[u].requests[v].push_back(i);
}
rep(i,1,320){
rep(j,i+1,320){
if(__gcd(i,j) == 1) coprime[i].push_back(j);
}
}
for (int i = m; i >= 320; --i){
for(int j = 1; j*i <= n; j++){
for(int k:coprime[j]){
if(k*i > n) break;
merge(i*j,i*k,m-i+1);
}
}
}
for (int i = min(m,319); i >= 1; --i){
set<int> tm;
for(int j = i; j <= n; j += i){
tm.insert(home(j));
}
int fir = *tm.begin();
for(int w:tm){
if(w == fir) continue;
merge(fir,w,m-i+1);
}
}
rep(i,0,q){
cout << ans[i] << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
19 ms |
11776 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
13816 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
116 ms |
21880 KB |
Output is correct |
| 2 |
Correct |
108 ms |
20088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
184 ms |
27200 KB |
Output is correct |
| 2 |
Correct |
152 ms |
24056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
132 ms |
21212 KB |
Output is correct |
| 2 |
Correct |
133 ms |
20984 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
161 ms |
23032 KB |
Output is correct |
| 2 |
Correct |
156 ms |
22008 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
269 ms |
28732 KB |
Output is correct |
| 2 |
Correct |
226 ms |
25452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
266 ms |
26488 KB |
Output is correct |
| 2 |
Correct |
435 ms |
35040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
466 ms |
37144 KB |
Output is correct |
| 2 |
Correct |
520 ms |
39476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
621 ms |
43208 KB |
Output is correct |
| 2 |
Correct |
587 ms |
41848 KB |
Output is correct |
