1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define maxn 500005
using namespace std;
int num[maxn],ans[maxn],n;
int big[maxn],pre[maxn];
struct node{
int l,r,id;
bool operator < (const node &u) const{
return l > u.l;
}
}p[maxn];
inline int lowbit(int x) {return x&(-x);}
inline void update(int x,int val){
while(x<=n){
big[x] = max(big[x],val);
x += lowbit(x);
}
}
inline int query(int x){
int ret = 0;
while(x){
ret = max(ret,big[x]);
x -= lowbit(x);
}
return ret;
}
int main(){
int t,q;
cin >> t;
while (t--){
cin >> n;
for (int i = 1; i <= n; ++i){
scanf("%d", &num[i]);
}
scanf("%d", &q);
for (int i = 0; i < q; ++i){
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i + 1;
}
sort(p,p+q);
int k = 0;
memset(big,0,sizeof(big));memset(pre,0,sizeof(pre));
for (int i = n; i >= 1; --i){
for (int j = 1; j*j <= num[i]; ++j){
if (num[i] % j == 0){
if (pre[j]) update(pre[j],j);
pre[j] = i;
if (j*j == num[i]) continue;
if (pre[num[i]/j]) update(pre[num[i]/j],num[i]/j);
pre[num[i]/j] = i;
}
}
for(;p[k].l == i;k++) ans[p[k].id] = query(p[k].r);
}
for (int i = 1; i <= q; ++i){
printf("%dn", ans[i]);
}
}
return 0;
}
|