题解 P1890 【gcd区间】
frankchenfu
2019-07-18 11:09:19
不得不说，~~这是一道线段树好题~~。
一看到这道题就想到了线段树——但是询问有$10^6$，怎么办？
哈！**zkw线段树，满足您的的各种~~卡常需求~~**！
实测zkw线段树在只有区间加、区间`max/min`的时候可以跑过$1.8\times 10^7$次操作（包括区间查询和单点修改）；
而如果加上一些$\log$级别的询问，一般也可以过$5\times 10^6$的数据。
等一下……这道题不需要修改？那么预处理是$n=1000$的$n\log_2 n$，查询是$m\log_2 n\times \ln n$（`gcd`复杂度）。
因此这道题就可以zkw线段树快速解决。
顺带提醒一下楼下的几位dalao：~~你们都知道可以用线段树了还不写zkw，难道你准备被noip的老爷机卡常吗？？？~~
```cpp
#include<cstdio>
#include<cstring>
const int MAXN=4010;
int d[MAXN];
int n,m,bit;
int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
void build(int n){
for(bit=1;bit<=n+1;bit<<=1);
for(int i=bit+1;i<=bit+n;i++)
scanf("%d",&d[i]);
for(int i=bit-1;i;i--)
d[i]=gcd(d[i<<1],d[i<<1|1]);
}
void update(int x,int y){
for(d[x+=bit]=y,x>>=1;x;x>>=1)
d[x]=gcd(d[x<<1],d[x<<1|1]);
}
int query(int s,int t){
int ans=d[s+bit];
for(s+=bit-1,t+=bit+1;s^t^1;s>>=1,t>>=1){
if(~s&1)
ans=gcd(ans,d[s^1]);
if(t&1)
ans=gcd(ans,d[t^1]);
}
return ans;
}
int main(){
scanf("%d%d",&n,&m);
build(n);
for(int i=1;i<=m;i++){
int l,r;scanf("%d%d",&l,&r);
printf("%d\n",query(l,r));
}
return 0;
}
```