|
题意：给你N个数字，每次询问一个区间[ l , r ],输出区间内某两个数的最大公约数。
思路：记录下询问的区间，排序，这里我是按l从大到小排的，方法很多种。
从后开始往前扫，从n - 1,每次扫到一个a[i],求出他所有的约数。
这里用一个数组vis记录这个约数上次出现的位置，这样就可以保证每次插入这个约数时，这个区间内至少是有两个这个约数的，也就是他至少是两个数的公约数。
然后查询这个区间内的最大值。
理解之后其实蛮水的。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos（-1.0）
#define Max 2505
#define inf 1《28
#define LL（x） （ x 《 1 ）
#define RR（x） （ x 《 1 | 1 ）
#define REP（i,s,t） for（ int i = （ s ） ; i <= （ t ） ; ++ i ）
#define ll long long
#define mem（a,b） memset（a,b,sizeof（a））
#define mp（a,b） make_pair（a,b）
#define PII pair<int,int>
using namespace std;
inline void RD（int &ret） {
char c;
do {
c = getchar（）；
} while（c < '0' || c > '9'） ;
ret = c - '0';
while（（c=getchar（）） >= '0' && c <= '9'）
ret = ret * 10 + （ c - '0' ）；
}
inline void OT（int a） {
if（a >= 10）OT（a / 10） ;
putchar（a % 10 + '0'） ;
}
#define N 50005
int n , m ;
int a[N] ;
int c[N] ;
int ans[N] ;
struct QU {
int s , e , id ;
} Q[N] ;
bool cmp（const QU& aa ,const QU& bb） {
return aa.s > bb.s ;
}
int vis[N] ;
void update（int pos ,int num） {
for （int i = pos ; i <= n ; i += i & （-i））{
if（c[i] < num）c[i] = num ;
}
}
int sum（int pos） {
int ans = 0 ;
for （int i = pos ; i >= 1 ; i -= i & （-i））{
if（ans < c[i]）ans = c[i] ;
}
return ans ;
}
int main（） {
int T ;
cin 》 T ;
while（T -- ） {
cin 》 n ;
mem（vis, 0） ;
mem（c ,0） ;
REP（i , 1 , n ） {
RD（a[i]） ;
}
cin 》 m ;
REP（i , 0 , m - 1） {
RD（Q[i].s） ;
RD（Q[i].e） ;
Q[i].id = i ;
}
sort（Q, Q + m , cmp） ;
int j = 0 ;
int i = n ;
while（1） {
while（i > 0 && Q[j].s <= i） {
for （int j = 1 ; j * j <= a[i] ; j ++ ） {
if（a[i] % j）continue ;
int k = a[i] / j ;
if（vis[j]）update（vis[j] , j） ;//vis数组表示这个约数j上次出现的位置，所以上上个位置插入j,因为上次出现过了，所以约数j的数量肯定大于等于2
if（k != j && vis[k]） {
update（vis[k] , k） ;
}
vis[j] = i ;
vis[k] = i ;
}
i --;
}
while（Q[j].s > i && j < m） {
ans[Q[j].id] = sum（Q[j].e） ;
j ++ ;
}
if（j >= m）break ;
}
REP（i , 0 , m - 1 ） {
printf（"%d\n",ans[i]） ;
}
}
return 0 ;
} |