题意：Given you a sequence of number a1, a2, ..., an.They are also a permutation of 1...n.
You need to answer some queries,each with the following format:
If we chose two number a,b (shouldn't be the same) from interval [l,
r],what is the maximum gcd(a, b)? If there's no way to choose two
distinct number(l=r) then the answer is zero.
思路：这题的处理方式和hdu4358有点像。我们用一个pre[x]表示约数x的倍数上次出现的位置，将查询按区间的右节点升序排序。num[i]的约 数为j，如果pre[j]为0，就将pre[j]置为i;否则就update(pre[j],j)，表示的意思是约数j肯定不是第一次出现,将 pre[j]以前的区间更新最大约数。如果查询区间的右边界在i处，那么左边界在pre[j]以前就肯定就能取到j。因为num[pre[j]]和 num[i]有一个公共约数j，且pre[j]和i被该查询区间所覆盖。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define Maxn 50010 6 #define lowbit(x) (x&(-x)) 7 using namespace std; 8 int C[Maxn],n,num[Maxn],pre[Maxn],q,ans[Maxn]; 9 struct QT{ 10 int l,r,i; 11 int operator <(const QT &temp) const 12 { 13 return r<temp.r; 14 } 15 }qt[Maxn]; 16 int Sum(int pos)//往后找 17 { 18 int sum=0; 19 while(pos<=n) 20 { 21 sum=max(sum,C[pos]); 22 pos+=lowbit(pos); 23 } 24 return sum; 25 } 26 void update(int pos,int val)//更新pos以前的位置 27 { 28 while(pos) 29 { 30 C[pos]=max(C[pos],val); 31 pos-=lowbit(pos); 32 } 33 } 34 int main() 35 { 36 int t,i,j; 37 scanf("%d",&t); 38 while(t--) 39 { 40 memset(C,0,sizeof(C)); 41 memset(pre,0,sizeof(pre)); 42 scanf("%d",&n); 43 for(i=1;i<=n;i++) 44 scanf("%d",num+i); 45 scanf("%d",&q); 46 for(i=1;i<=q;i++) 47 { 48 scanf("%d%d",&qt[i].l,&qt[i].r); 49 qt[i].i=i; 50 } 51 sort(qt+1,qt+1+q); 52 int r=1; 53 for(i=1;i<=n;i++) 54 { 55 if(r>q) break; 56 for(j=1;j*j<=num[i];j++) 57 { 58 if(num[i]%j) continue; 59 if(pre[j]) update(pre[j],j); 60 pre[j]=i; 61 if(j*j==num[i]) break; 62 int k=num[i]/j; 63 if(pre[k]) update(pre[k],k); 64 pre[k]=i; 65 } 66 while(qt[r].r==i&&r<=q) 67 { 68 ans[qt[r].i]=Sum(qt[r].l); 69 r++; 70 } 71 } 72 for(i=1;i<=q;i++) 73 printf("%d ",ans[i]); 74 } 75 return 0; 76 }