思路参考 。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 const int MAXN = 50010; 9 10 struct node 11 { 12 int l, r; 13 int idx; 14 }; 15 16 node Qry[MAXN]; //查询 17 int C[MAXN]; //树状数组 18 int vis[MAXN]; // i 的倍数上一次出现的位置 19 int num[MAXN]; //原数组 20 int ans[MAXN]; //答案 21 int N, Q; 22 23 bool cmp( node a, node b ) 24 { 25 return a.l > b.l; 26 } 27 28 int lowbit( int x ) 29 { 30 return x & (-x); 31 } 32 33 int query( int x ) 34 { 35 int res = 0; 36 while ( x > 0 ) 37 { 38 res = max( res, C[x] ); 39 x -= lowbit(x); 40 } 41 return res; 42 } 43 44 void Add( int x, int val ) 45 { 46 while ( x <= N ) 47 { 48 C[x] = max( C[x], val ); 49 x += lowbit(x); 50 } 51 return; 52 } 53 54 int main() 55 { 56 int T; 57 scanf( "%d", &T ); 58 while ( T-- ) 59 { 60 scanf( "%d", &N ); 61 for ( int i = 1; i <= N; ++i ) 62 scanf( "%d", &num[i] ); 63 64 scanf( "%d", &Q ); 65 for ( int i = 0; i < Q; ++i ) 66 { 67 scanf("%d%d", &Qry[i].l, &Qry[i].r ); 68 Qry[i].idx = i; 69 } 70 71 sort( Qry, Qry + Q, cmp ); 72 memset( C, 0, sizeof(C) ); 73 memset( vis, 0, sizeof(vis) ); 74 75 int i = 0, j = N; 76 while ( i < Q ) 77 { 78 while ( j > 0 && j >= Qry[i].l ) 79 { 80 for ( int k = 1; k*k <= num[j]; ++k ) 81 { 82 if ( num[j] % k == 0 ) 83 { 84 if ( vis[k] ) 85 { 86 Add( vis[k], k ); 87 } 88 vis[k] = j; 89 90 int tmp = num[j] / k; 91 if ( tmp != k ) 92 { 93 if ( vis[tmp] ) 94 { 95 Add( vis[tmp], tmp ); 96 } 97 vis[tmp] = j; 98 } 99 }100 }101 --j;102 }103 104 ans[ Qry[i].idx ] = query( Qry[i].r );105 ++i;106 }107 108 for ( int i = 0; i < Q; ++i )109 printf( "%d\n", ans[i] );110 }111 return 0;112 }
n个数，如果把n个数的约数全部写出来。查询[l,r]之间的gcd的最大值，就相当于找一个最大的数，使得这个数是[l,r]之间至少是两个的约数。
对于一个数n,在sqrt(n)内可以找出所有约数。
我的做法是对查询进行离线处理。
将每个查询按照 l 从大到小排序。
然后 i 从 n~0 ,表示从后面不断扫这些数。
对于数a[i],找到a[i]的所有约数，对于约数x,在x上一次出现的位置加入值x.
这样的查询的时候，只要查询前 r 个数的最大值就可以了。