~~太暴力了~~
by 吾皇 @ 2019-08-14 20:47:22
建议暴力的时候二分，gcd等于1直接返回，左右端点相等直接返回；
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
int a[10011];
int gcd(int a,int b)
{
if(b==0)return a;
return gcd(b,a%b);
}
int ask(int l,int r)
{
if(l == r)return a[l];
int ans=a[l] ,tot = a[r];
int mid = (l + r) >> 1;
for(int i = r ; i >= mid + 1 ; i--){
ans = gcd(a[i],ans);
if(ans == 1)return 1;
}
for(int i = l + 1;i <= mid ; i++)
{
ans=gcd(a[i],ans);
if(ans == 1)return 1;
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
int t=ask(l,r);
printf("%d\n",t);
}
return 0;
}
```
by 放学后茶会 @ 2020-12-02 18:29:29
注意开氧气
by 放学后茶会 @ 2020-12-02 18:30:11