数论基础---gcd的更相减损术_gcd更相减损法

首先先把结论写出来。
$gcd(a,b)=gcd(a,b-a)$
$gcd(a,b,c)=gcd(a,b-a,c-b)$
$gcd(a_1,a_2,\dots a_n)=gcd(a_1,a_2-a_1,\dots a_n-a_{n-1})$

例题1：Codeforces Round #691 (Div. 2)—C. Row GCD
C. Row GCD
$题意：给你两个数组a和b,对于j=1,...,m,找出a_1+b_j,...,a_n+b_j的gcd.$
题解：根据上面的结论可得：
$gcd((a_1+b_j),(a_2+b_j),...,(a_n+b_j))=gcd(a_1+b_j,a_2-a_1,...,a_n-a_{n-1}).$

所以我们先对a数组求出他差分数组的gcd，设他为d 也就是$d=gcd(a_2-a_1,a_3-a_2,....,a_n-a_{n-1});$
所以我们每次求$gcd(a_1+b_j,gcd(d))$

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;

#define int long long

int a[maxn],b[maxn];
signed main()
{
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    //sort(a+1,a+n+1);
    int gcd=a[2]-a[1];
    if(n==1) gcd=0;
    for(int i=2;i<=n;i++){
        gcd=__gcd(gcd,a[i]-a[i-1]);
    }
    for(int i=1;i<=m;i++){
        cout<<abs(__gcd(gcd,a[1]+b[i]))<<" ";
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

例题2：牛客小白月赛16 —小阳的贝壳
小阳的贝壳

$gcd(a_1,a_2,\dots a_n)=gcd(a_1,a_2-a_1,\dots a_n-a_{n-1})$
题解：
图片来自巨雨的题解。

维护这个数组的差分序列。
操作一：因为是个差分数组，我们只需要给l端点加x，r+1端点的值-x即可。
操作二：我们只有得到这个差分数组的最大值即可。（不要忘记abs）
操作三：
求$gcd(a_l,a_{l+1},\dots a_r)=gcd(a_l,a_{l+1}-a_l,\dots a_r-a_{r-1})$
设$k=gcd(a_{l+1}-a_l,\dots a_r-a_{r-1})$
也就是求$gcd(a_l,k)；即可$
查询$a_l$也就是查询差分数组$1-l$的和。

也就是相当于单点修改 区间查询。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define endl '\n'
#define int long long
const int maxn=1e5+10;

int a[maxn<<2];
int imax[maxn<<2];
int gcd[maxn<<2];
int sum[maxn<<2];

void push_up(int node){
    sum[node]=sum[node*2+1]+sum[node*2];
    gcd[node]=__gcd(gcd[node*2+1],gcd[node*2]);
    imax[node]=max(imax[node*2],imax[node*2+1]);
}

void build(int node,int start,int ends){
    if(start==ends){
        sum[node]=a[start];
        gcd[node]=abs(a[start]);
        imax[node]=abs(a[start]);
        return ;
    }
    int mid=(start+ends)/2;
    build(node*2,start,mid);
    build(node*2+1,mid+1,ends);
    push_up(node);
}
void update(int node,int start,int ends,int pos,int val){
    if(start==ends){
        sum[node]+=val;
        gcd[node]=abs(sum[node]);
        imax[node]=abs(sum[node]);
        return ;
    }
    int mid=(start+ends)/2;
    if(pos<=mid) update(node*2,start,mid,pos,val);
    else update(node*2+1,mid+1,ends,pos,val);
    push_up(node);
}
int get_sum(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r){
        return sum[node];
    }
    int ans=0;
    int mid=(start+ends)/2;
    if(l<=mid) ans+=get_sum(node*2,start,mid,l,r);
    if(mid<r) ans+=get_sum(node*2+1,mid+1,ends,l,r);
    return ans;
}
int get_imax(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r){
        return imax[node];
    }
    int mid=(start+ends)/2;
    int ans=-1e15;
    if(l<=mid) ans=max(ans,get_imax(node*2,start,mid,l,r));
    if(mid<r) ans=max(ans,get_imax(node*2+1,mid+1,ends,l,r));
    return ans;
}
int get_gcd(int node,int start,int ends,int l,int r){
    if(start>=l&&ends<=r){
        return gcd[node];
    }
    int mid=(start+ends)/2;
    int ans=0;
    if(l<=mid) ans=__gcd(ans,get_gcd(node*2,start,mid,l,r));
    if(mid<r) ans=__gcd(ans,get_gcd(node*2+1,mid+1,ends,l,r));
    return ans;
}

signed main(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=n;i>=1;i--){
        a[i]=a[i]-a[i-1];
    }
    build(1,1,n);
    for(int i=0;i<m;i++){
        int opt,l,r,x;
        cin>>opt;
        if(opt==1){
            cin>>l>>r>>x;
            update(1,1,n,l,x);
            if(r+1<=n) update(1,1,n,r+1,-x);
        }
        else if(opt==2){
            cin>>l>>r;
            if(l==r){
                cout<<0<<endl;
                continue;
            }
            int ans=get_imax(1,1,n,l+1,r);
            cout<<ans<<endl;
        }
        else if(opt==3){
            cin>>l>>r;
            if(l==r) cout<<get_sum(1,1,n,1,l)<<endl;
            else{
                x=get_sum(1,1,n,1,l);
                cout<<__gcd(x,get_gcd(1,1,n,l+1,r))<<endl;
            }
        }
    }
    return 0;
}




1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113