@[lsy263](/space/show?uid=72611)
~~话说这题写线段树好像有点杀鸡用牛刀~~
qwq这题是**没有修改**的
即：本题是**静态的区间查询**
也就是说，写一个$ST$表远比写一个线段树来得快，而且代码量和编程难度更小
所以嘛。。。劝你写一写$ST$表
反正都是$O(nlogn)$也不怕什么qwq
by ___new2zy___ @ 2018-10-30 07:10:36
@[___new2zy___](/space/show?uid=60359) 是呢那我现在学吧
by lsy263 @ 2018-10-30 22:07:33
线段树水过-----
```cpp
#include <iostream>
#include <cstdio>
#define maxn 1005
using namespace std;
struct Tree {int l, r, val;} tree[maxn*4];
int n, q, flag, gcdd;
int a[maxn];
int gcd(int a, int b)
{
if(!b) return a;
else return gcd(b, a%b);
}
void build(int root, int l, int r)
{
tree[root].l=l, tree[root].r=r;
if(l==r) {tree[root].val=a[l]; return;}
int mid=(l+r)>>1;
build(root<<1, l , mid),build(root<<1|1, mid+1, r);
tree[root].val=gcd(tree[root<<1].val, tree[root<<1|1].val);
}
void ask(int root, int l, int r)
{
if(l<=tree[root].l && tree[root].r<=r)
{
if(!flag) flag=1, gcdd=tree[root].val;
else gcdd=gcd(gcdd, tree[root].val);
return;
}
int mid=(tree[root].l+tree[root].r)>>1;
if(l<=mid) ask(root<<1, l, r);
if(r>mid) ask(root<<1|1, l, r);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build(1, 1, n);
for(int i=1;i<=q;i++)
{
flag=0;
int l, r; cin>>l>>r;
ask(1, l, r);
printf("%d\n",gcdd);
}
return 0;
}
```
by Error_666 @ 2018-10-30 22:55:03
@[lsy263](/space/show?uid=72611)
by Error_666 @ 2018-10-30 22:55:13
再附上ST表写法
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 1005
using namespace std;
int n, q, logMax;
int a[maxn];
int f[maxn][31];
int gcd(int a, int b)
{
if(!b) return a;
else return gcd(b, a%b);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>q, logMax=(int)log2(n);
for(int i=1;i<=n;i++) cin>>a[i], f[i][0]=a[i];
for(int j=1;j<=logMax;j++)
for(int i=1;i<=n-(1<<j)+1;i++)
f[i][j]=gcd(f[i][j-1], f[i+(1<<(j-1))][j-1]);
for(int i=1;i<=q;i++)
{
int l, r; cin>>l>>r;
int p=(int)log2(r-l+1);
printf("%d\n",gcd(f[l][p], f[r-(1<<p)+1][p]));
}
return 0;
}
```
by Error_666 @ 2018-10-30 23:13:56
分块也来一发吧qwq
```cpp
#include <iostream>
#include <cstdio>
#include <cmath>
#define maxn 1005
using namespace std;
struct Block {int l, r, val;} block[maxn];
int n, q, sizeBlock, numBlock, gcdd;
int a[maxn], belong[maxn];
int gcd(int a, int b)
{
if(!b) return a;
else return gcd(b, a%b);
}
void build()
{
sizeBlock=(int)sqrt(n);
numBlock=n/sizeBlock;
if(n%sizeBlock) numBlock++;
for(int i=1;i<=numBlock;i++)
block[i].l=(i-1)*sizeBlock+1, block[i].r=i*sizeBlock;
block[numBlock].r=n;
for(int i=1;i<=n;i++) belong[i]=(i-1)/sizeBlock+1;
for(int i=1;i<=numBlock;i++)
{
gcdd=a[block[i].l];
if(belong[block[i].l+1]!=belong[block[i].l]) block[i].val=gcdd;
else
for(int j=block[i].l+1;j<=block[i].r;j++)
block[i].val=gcd(gcdd, a[j]);
}
}
int ask(int l, int r)
{
int gcdd=a[l];
if(belong[l]==belong[r])
{
for(int i=l+1;i<=r;i++) gcdd=gcd(gcdd, a[i]);
return gcdd;
}
for(int i=l+1;i<=block[belong[l]].r;i++) gcdd=gcd(gcdd, a[i]);
for(int i=block[belong[r]].l;i<=r;i++) gcdd=gcd(gcdd, a[i]);
for(int i=belong[l]+1;i<belong[r];i++) gcdd=gcd(gcdd, block[i].val);
return gcdd;
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>a[i];
build();
for(int i=1;i<=q;i++)
{
int l, r; cin>>l>>r;
printf("%d\n",ask(l, r));
}
return 0;
}
```
by Error_666 @ 2018-10-30 23:38:45
@[BigYellowDog](/space/show?uid=91681) 还行哈
```
BYD是用文本框写代码而AK的唯一的人
```
by lsy263 @ 2018-10-30 23:49:59
@[BigYellowDog](/space/show?uid=91681) 就是因为你，我也写了一遍，浪费的时间精力你怎么赔偿qwq
[click](https://www.luogu.org/blog/15lsy/solution-p1890)
```
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1002;
int n,st[N][21],a[N];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void ini()
{
for(int i=1;i<=n;++i) st[i][0]=a[i];
for(int j=1;j<=log2(n);j++)
for(int i=1;i+(1<<j)-1<=n;i++) //i+(1<<j)-1 区间的末尾<=n
st[i][j]=gcd(st[i][j-1], st[i+(1<<(j-1))][j-1]);
}
int ask(int l,int r)
{
int p=log2(r-l+1);
return gcd(st[l][p],st[r-(1<<p)+1][p]);
//从左端找&从右端找
//有重叠但显然没有关系
}
int main()
{
int m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
ini();
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y));
}
return 0;
}
```
```
#include<iostream>
#include<algorithm>
#include<stdio.h>
#define LS rt<<1,l,mid
#define RS rt<<1|1,mid+1,r
#define PushUp tree[rt].gcd=gcd(tree[rt<<1].gcd,tree[rt<<1|1].gcd)
using namespace std;
const int N=100002;
int a[N];
int gcd(int a,int b)
{return !b?a:gcd(b,a%b);}
struct Tr{int l,r,gcd;}tree[N];
void build(int rt,int l,int r)
{
tree[rt].l=l,tree[rt].r=r;
if(l==r)
{
tree[rt].gcd=a[l];
return;
}
int mid=(l+r)>>1;
build(LS);build(RS);
PushUp;
}
int find(int rt,int l,int r)
{
if(l<=tree[rt].l&&r>=tree[rt].r)
return tree[rt].gcd;
int mid=(tree[rt].l+tree[rt].r)>>1;
int r1=0,r2=0;
if(l<=mid) r1=find(rt<<1,l,r);
if(r>mid) r2=find(rt<<1|1,l,r);
if(!r1) return r2; //左边查不到
if(!r2) return r1; //同理
if(r1&&r2) return gcd(r1,r2); //都查到了
}
int n,m;
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
build(1,1,n);
int x,y;
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",find(1,x,y));
}
return 0;
}
```
```
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=1002;
int gcd(int a,int b)
{return !b?a:gcd(b,a%b);}
int block,belong[N],num,l[N],r[N],fk[N];
int n,a[N];
void ini()
{
block=(int)sqrt(n);
num=n/block;
if(n%block) num++;
for(int i=1;i<=n;++i)
belong[i]=(i-1)/block+1;
for(int i=1;i<=num;++i)
l[i]=(i-1)*block+1,r[i]=i*block,fk[i]=a[l[i]];
r[num]=n;
for(int i=1;i<=n;++i)
if(i!=l[belong[i]])
fk[belong[i]]=gcd(a[i],fk[belong[i]]);
}
int ask(int x,int y)
{
int ans;
if(belong[x]==belong[y])
{
ans=a[x];
for(int i=x+1;i<=y;++i)
ans=gcd(ans,a[i]);
return ans;
}
else
{
ans=a[x];
for(int i=x+1;i<=r[belong[x]];++i) ans=gcd(ans,a[i]);
for(int i=l[belong[y]];i<=y;++i) ans=gcd(ans,a[i]);
for(int i=belong[x]+1;i<belong[y];++i) ans=gcd(ans,fk[i]);
return ans;
}
}
int main()
{
int m,x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
ini();
while(m--)
{
scanf("%d%d",&x,&y);
printf("%d\n",ask(x,y));
}
return 0;
}
```
by lsy263 @ 2018-11-01 23:56:45
真的是！写线段树也不写zkw线段树，想被卡常吗？？？
```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;
}
```
by frankchenfu @ 2019-07-18 11:12:01
？各位plqtj吗，举办了
by zhzkiller @ 2023-08-05 10:44:52