AcWing 246. 区间最大公约数

差分
(gcd)

证明：(gcd(a_1,a_2,a_3,...,a_n)=gcd(a_1,a_2-a_1,a_3-a_2,...,a_n-a_{n-1})).
为方便描述令 (c_1=a_1,c_i=a_i-a_{i-1},i>1).
设其最大公约数为 (d) , 则 (d|a_1,d|a_2,..., --> d|(a_2-a_1)...)
左边(=d);
右边(=d imes gcd(c_1/d,c_2/d,...))
引理：(gcd(c_1/d,c_2/d,...)=1)
反证法：若 (gcd(c_1/d,c_2/d,...)=k,k>1).

则 (a_1/d=c_1/d=x imes k)
(c_2/d=(a_2-a_1)/d=y imes k)
(a_2/d=(a_1+c_2)/d=x imes k + y imes k=(x+y) imes k),(k|a_2)
...
同理得 (k|(a_i/d),i in [1,n])

则 (gcd(a_1,a_2,a_3,...,a_n)=d imes k).
与题设不符，舍去。

所以 (gcd(c_1/d,c_2/d,...)=1)。
右边$=d imes gcd(c_1/d,c_2/d,...)= d = $ 左边。

即证。

Code：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>

using namespace std;
typedef long long LL;
const int N=5e5+5;

LL a[N],c[N];
int n,m;

LL gcd(LL a,LL b) 
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
#define lc (now<<1)
#define rc (now<<1|1)
LL sum[4*N],d[4*N];
void Update(int now,int pos,LL key,int l,int r)
{
    if(l==r&&l==pos) {
        sum[now]+=key;
        d[now]+=key;
        return;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) Update(lc,pos,key,l,mid);
    else Update(rc,pos,key,mid+1,r);

    sum[now]=sum[lc]+sum[rc];
    d[now]=gcd(d[lc],d[rc]);
}

LL QuerySum(int now,int pos,int l,int r)
{
    if(r<=pos) return sum[now];
    int mid=(l+r)>>1;
    LL res=QuerySum(lc,pos,l,mid);
    if(pos>=mid+1) res+=QuerySum(rc,pos,mid+1,r);
    return res;
}

LL QueryGcd(int now,int x,int y,int l,int r)
{
    if(x<=l&&r<=y) return d[now];
    int mid=(l+r)>>1;
    LL res=0;
    if(x<=mid) res=gcd(res,QueryGcd(lc,x,y,l,mid));
    if(y>=mid+1) res=gcd(res,QueryGcd(rc,x,y,mid+1,r));
    return res;
}


int main()
{
    int i;
    int x,y;
    LL z;
    char opt;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++) {
        scanf("%lld",&a[i]);
        c[i]=a[i]-a[i-1];
        Update(1,i,c[i],1,n);
    }
    while(m--) {
        for(opt=getchar();opt!='C'&&opt!='Q';opt=getchar());
        scanf("%d%d",&x,&y);
        if(opt=='Q') printf("%lld
",abs(gcd(QueryGcd(1,x+1,y,1,n),QuerySum(1,x,1,n))));
        else {
            scanf("%lld",&z);
            Update(1,x,z,1,n);
            if(y+1<=n) Update(1,y+1,-z,1,n);
        }
    }
    return 0;
}

AcWing 246. 区间最大公约数

相关推荐