题解 P1890 【gcd区间】

嘉年华 · 2019-12-10 17:45:56 · 题解

分块

这道题其实是道水题（我做了一个中午）。 首先，我们发现这道题是一个区间查询问题，所以我们自然就想到了各种区间算法。 但是这道题的n很小，而m很大，又不带修改，如果我们用线段树来做这道题查询是O(log n),而分块则是O(sqrt(n)),在n=1000的情况下，两者相差只有约4倍，可以当做是常数级别的差异，而且线段树还要O(nlog n)，前几个点还不一定比分块快，所以我们可以轻松愉快的用分块算法快速解决这个问题了。 AC代码如下:

#include<bits/stdc++.h>
using namespace std;
#define qj 40

int n,m,L,R,ans;
int a[1010],q[(1010/qj)+10];
int maxn=0,tt=0;

inline int read_(void)
{
    int num=0,f=1;
    char ch=getchar();
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-') ch=getchar(),f=-1;
    while(ch>='0'&&ch<='9') num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return f*num;
}

inline int gcd(int x,int y)
{
    if(min(x,y)==0) return max(x,y);
    return gcd((max(x,y)%min(x,y)),min(x,y));
}

inline void print(int num)
{
    if(num<0)
    {
        putchar('-');
        num=abs(num);
    }
    if(num==0) return;
    int f=num%10;
    print(num/10);
    putchar(f+'0');
    return;
}

int main(void)
{
    n=read_(),m=read_();
    for(int i=1;i<=n;i++) a[i]=read_();
    for(int l=1;l*qj<n;++l)
    {
        q[l]=a[(l-1)*qj+1];
        for(int i=(l-1)*qj+2;i<=l*qj;++i) q[l]=gcd(q[l],a[i]);
    }
    while(m--)
    {
        L=read_(),R=read_();
        int st=L/qj+2,en=R/qj;
        ans=a[L];
        for(int i=st;i<=en;++i) ans=gcd(ans,q[i]);
        for(int i=L;i<=min((st-1)*qj,R);++i) ans=gcd(ans,a[i]);
        for(int i=max(L,en*qj+1);i<=R;++i) ans=gcd(ans,a[i]);
        print(ans);
        printf("\n");
    }
    return 0;
}