# JZOJ – 5782 城市猎人

Time Limit : 1500ms
Memory Limit : 64MB

## Sample Input

### Case 1

8 3 3
2 5
3 6
4 8


### Case 2

25 6 1
20 9


### Case 3

9999 2222 2
1025 2405
3154 8949


## Sample Output

### Case 1

3
1
2


### Case 2

4


### Case 3

1980
2160


## 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>

using namespace std;
const int MAXN = 200000 + 10;

int x  = 0;
char ch = getchar();

while(ch < '0' || ch > '9'){
ch = getchar();
}

while('0' <= ch && ch <= '9'){
x = x*10 + ch - '0';
ch = getchar();
}

return x;
}

int f[MAXN], val[MAXN];
int tree[MAXN][2], grand[MAXN][21], deep[MAXN], cnt;
int n, m, q;

inline int get(int x){
int root = x;
while(root != f[root]){
root = f[root];
}

while(x != root){
int tmp = f[x];
f[x] = root;
x = tmp;
}

return root;
}

inline void merge(int a, int b, int v){
int f_a = get(a);
int f_b = get(b);

if(f_a == f_b)
return;

cnt++;

int nowroot = n + cnt;

f[f_a] = nowroot;
f[f_b] = nowroot;
f[nowroot] = nowroot;

val[nowroot] = v;
tree[nowroot][0] = f_a;
tree[nowroot][1] = f_b;

}

inline void dfs(int x){
for(register int i=1; i<=19; i++)
grand[x][i] = grand[grand[x][i-1]][i-1];

for(register int i=0; i<2; i++){
int v = tree[x][i];

if(v){
deep[v] = deep[x]+1;
grand[v][0] = x;

dfs(v);
}
}
}

inline int LCA(int a, int b){
if(deep[a] < deep[b])
swap(a, b);

for(register int i=19; i>=0; i--){
if(deep[grand[a][i]] >= deep[b]){
a = grand[a][i];
}
}

if(a == b)
return a;

for(register int i=19; i>=0; i--){
if(grand[a][i] != grand[b][i]){
a = grand[a][i];
b = grand[b][i];
}
}

if(a == b)
return a;
else
return grand[a][0];
}
int main(){

freopen("pictionary.in", "r", stdin);
freopen("pictionary.out", "w", stdout);

for(register int i=1; i<=n; i++)
f[i] = i;

for(register int gcd=m; gcd>=1; gcd--){
int time = m - gcd + 1;

for(register int k=2*gcd; k <= n; k+=gcd)
merge(gcd, k, time);
}

deep[n+cnt] = 1;
grand[n+cnt][0] = n+cnt;

dfs(n+cnt);

for(register int i=1; i<=q; i++){