题解 CF2050F

· · 题解

题意：

给定一个序列，每次询问求区间同余最大模数。

思路：

发现一些有趣的性质：考虑一个区间，如果所有数除以某个模数的余数相同，所有数之间的差一定是这个模数的倍数。反之我们有：使得区间内所有数同余的模数是区间差分的最大公约数。

区间 gcd 可以被线段树合并，于是开线段树，每次询问直接查询即可（注意区间内所有数相等时答案是 0）。复杂度 O(n\log n)。

程序如下：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int T,n,q,a[N];
int bet[N],t[N*4];
int gcd(int a,int b){
    if(a==0&&b==0)return 0;
    return __gcd(a,b);
}
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
void pushup(int x){t[x]=gcd(t[ls(x)],t[rs(x)]);}
void build(int x,int l,int r){
    if(l==r){
        t[x]=bet[l];
        return;
    }
    int mid=(l+r)>>1;
    build(ls(x),l,mid);
    build(rs(x),mid+1,r);
    pushup(x);
}
int query(int x,int l,int r,int L,int R){
    if(L<=l&&R>=r)return t[x];
    int mid=(l+r)>>1;
    if(L<=mid&&R<=mid)return query(ls(x),l,mid,L,R);
    else if(L>mid&&R>mid)return query(rs(x),mid+1,r,L,R);
    else return gcd(query(ls(x),l,mid,L,R),query(rs(x),mid+1,r,L,R));
}
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            if(i>1)bet[i-1]=abs(a[i]-a[i-1]);
        }
        if(n>1)build(1,1,n-1);
        while(q--){
            int l,r;
            scanf("%d%d",&l,&r);
            if(l==r)printf("0 ");
            else printf("%d ",query(1,1,n-1,l,r-1));
        }
        puts("");
    }
    return 0;
}

THE END