首页 > 代码库 > HDU 4630 No Pain No Game

HDU 4630 No Pain No Game

2024-07-15 15:27:57   221人阅读

No Pain No Game

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1465    Accepted Submission(s): 631


Problem Description
Life is a game,and you lose it,so you suicide.
But you can not kill yourself before you solve this problem:
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.
 

 

Input
First line contains a number T(T <= 5),denote the number of test cases.
Then follow T test cases.
For each test cases,the first line contains a number n(1 <= n <= 50000).
The second line contains n number a1, a2, ..., an.
The third line contains a number Q(1 <= Q <= 50000) denoting the number of queries.
Then Q lines follows,each lines contains two integer l, r(1 <= l <= r <= n),denote a query.
 

 

Output
For each test cases,for each query print the answer in one line.
 

 

Sample Input
1
10
8 2 4 9 5 7 10 6 1 3
5
2 10
2 4
6 9
1 4
7 10
 
Sample Output
5
2
2
4
3
Source
2013 Multi-University Training Contest 3
 
  1 /**  2 题意：求解区间[ L , R ]   max gcd() ;  3   4 如果只求一次，那么我们可以这样做。  5 把每个数字的因子刷一遍，满足>=2的最大就是结果。  6 如果多次，可以这样求解。  7 在区间[ L , R ] 如果素因子出现，更新它上次出现的位置的最大值，  8 保存当前出现的位置。第一次出现不更新，只保存。  9  10 当枚举到R的时候，我们就可以在[ L, R ]中找最大值即可。 11  12 所以这一题就可以对r 排序，然后进行更新。 13 **/ 14 #include<iostream> 15 #include<stdio.h> 16 #include<cstring> 17 #include<cstdlib> 18 #include<algorithm> 19 #include<vector> 20 using namespace std; 21  22 vector<int>yz[50002]; 23 struct node 24 { 25     int l,r,len; 26     int maxn; 27 }f[50002*4]; 28 struct node2 29 { 30     int st,ed; 31     int i,val; 32 }a[50002]; 33 int date[50002]; 34 int pre[50002]; 35  36 bool cmp(struct node2 n1,struct node2 n2) 37 { 38     return n1.ed<n2.ed; 39 } 40 bool cmp1(struct node2 n1,struct node2 n2) 41 { 42     return n1.i<n2.i; 43 } 44 void init() 45 { 46     for(int i=1;i<=50000;i++) 47         for(int j=i;j<=50000;j=j+i) 48         yz[j].push_back(i); 49 } 50 void build(int l,int r,int n) 51 { 52     int mid = (l+r)/2; 53     f[n].l = l; 54     f[n].r = r; 55     f[n].len = f[n].r-f[n].l +1; 56     f[n].maxn = 0; 57     if(l==r) return; 58     build(l,mid,n*2); 59     build(mid+1,r,n*2+1); 60 } 61 void update(int wz,int num,int n) 62 { 63     int mid=(f[n].l + f[n].r)/2; 64     if(f[n].l == wz && f[n].r == wz) 65     { 66         if(f[n].maxn<num) 67             f[n].maxn = num; 68         return; 69     } 70     if(mid>=wz) update(wz,num,n*2); 71     else if(mid<wz) update(wz,num,n*2+1); 72     f[n].maxn = f[n*2].maxn>f[n*2+1].maxn ? f[n*2].maxn : f[n*2+1].maxn; 73 } 74 int query(int l,int r,int n) 75 { 76     int mid=(f[n].l + f[n].r)/2; 77     if(f[n].l == l && f[n].r == r) 78     { 79         return f[n].maxn; 80     } 81     if(mid>=r) return query(l,r,n*2); 82     else if(mid<l) return query(l,r,n*2+1); 83     else return max(query(l,mid,n*2),query(mid+1,r,n*2+1)); 84 } 85 int main() 86 { 87     int T , n , m; 88     init(); 89     scanf("%d",&T); 90     while(T--) 91     { 92         scanf("%d",&n); 93         build(1,n,1); 94         for(int i=1;i<=n;i++) 95             scanf("%d",&date[i]); 96         scanf("%d",&m); 97         for(int i=1;i<=m;i++) 98         { 99             scanf("%d%d",&a[i].st,&a[i].ed);100             a[i].i = i;101             a[i].val = 0;102         }103         sort(a+1,a+1+m,cmp);104         memset(pre,0,sizeof(pre));105         int k = 1;106         for(int i=1;i<=n;i++)107         {108             int ans = yz[date[i]].size();109             for(int j=0;j<ans;j++)110             {111                 int temp = yz[date[i]][j];112                 if(pre[temp])113                     update(pre[temp],temp,1);114                 pre[temp] = i;115             }116             while(a[k].ed == i && k<=m)117             {118                 a[k].val = query(a[k].st,a[k].ed,1);119                 k++;120             }121         }122         sort(a+1,a+1+m,cmp1);123         for(int i=1;i<=m;i++)   printf("%d\n",a[i].val);124     }125     return 0;126 }

 

 

 


联系
我们