題意：給出一個n和1到n的某個排列，詢問q次，每次詢問[l,r]區間內任意挑兩個數，最大公約數的最大值是多少。

解題思路：記錄一個pre數組，pre[i]表示對於某個數i，已經出現過的它的倍數最近是在那個位置。將詢問按右端點排序。用樹狀數組維護從某一位置到maxn的最佳答案。從1到n開始掃描num[i]，sqrt(num[i])的復雜度去枚舉它的約數x，那麼我們可以用這個x去更新所有pre[x]以前的答案（能更新則更新，後綴數組維護一個最大值）。假如我們現在處理到了第k個詢問的右端點是i，因為我們還只處理到了i，所以對於左端點一直到maxn的最大值即第k個詢問的答案。

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std ;

const int maxn = 55555 ;
struct Ans
{
	int l , r , ans ;
} p[maxn] ;

int c[maxn] , pre[maxn] ;

int lowbit ( int x ) { return x & ( -x ) ; }

void update ( int pos , int v )
{
	while ( pos > 0 )
	{
		c[pos] = max ( c[pos] , v ) ;
		pos -= lowbit ( pos ) ;
	}
}

int query ( int pos )
{
	int ret = 0 ;
	while ( pos < maxn - 10 )
	{
		ret = max ( ret , c[pos] ) ;
		pos += lowbit ( pos ) ;
	}
	return ret ;
}

bool cmp ( int i , int j )
{
	return p[i].r < p[j].r ;
}
int pos[maxn] , num[maxn] ;

int main ()
{
	int cas , n , i , j , m ;
	scanf ( "%d" , &cas ) ;
	while ( cas -- )
	{
		memset ( c , 0 , sizeof ( c ) ) ;
		memset ( pre , 0 , sizeof ( pre ) ) ;
		scanf ( "%d" , &n ) ;
		for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ;
		scanf ( "%d" , &m ) ;
		for ( i = 1 ; i <= m ; i ++ )
		{
			scanf ( "%d%d" , &p[i].l , &p[i].r ) ;
			pos[i] = i ;
		}
		sort ( pos + 1 , pos + m + 1 , cmp ) ;
		int tot = 1 ;
		for ( i = 1 ; i <= n ; i ++ )
		{
			if ( tot > m ) break ;
			for ( j = 1 ; j * j <= num[i] ; j ++ )
			{
				if ( num[i] % j ) continue ;
				if ( pre[j] != 0 ) update ( pre[j] , j ) ;
				pre[j] = i ;
				if ( j * j == num[i] ) continue ;
				int k = num[i] / j ;
				if ( pre[k] != 0 ) update ( pre[k] , k ) ;
				pre[k] = i ;
			}
			while ( tot <= m && p[pos[tot]].r == i )
			{
				p[pos[tot]].ans = query ( p[pos[tot]].l ) ;
				tot ++ ;
			}
		}
		for ( i = 1 ; i <= m ; i ++ )
		{
			if ( p[i].l == p[i].r )
			{
				puts ( "0" ) ;
				continue ;
			}
			printf ( "%d\n" , p[i].ans ) ;
		}
	}
}