GCD

辗转相除法

证明

设实数 \(a\) 和 \(b\) ，我们要证明 $gcd(a,b) == gcd(b,a% b) $ 。

1. 证明 $gcd(a,b) | (a-b) $

   可以发现，\(a==km\) ，\(b==lm\) ，\((a-b)==(k-l)m \quad(m \in N^*)\) 。

   而 \(gcd(a,b)==m\)，易知 $gcd(a,b) | (a-b) $ 。

   同理 \(gcd(b,a-b)|a\) 。2.

2. 由 $ 1 $ 可得，\(gcd(a,b)\) 是 \(b,a-b\) 的公因数，且 \(gcd(a-b,b)\) 是 \(a,b\) 的公因数。由 \(gcd\) 的定义可知 \(gcd(a,b) \leq gcd(b,a-b)\) 且 \(gcd(a,b) \geq gcd(b,a-b)\)即 \(gcd(a,b) == gcd(b,a-b)\)。

3. 而 \(a\) 重复减去 \(b\) 其实就是 取模。

Code

很简单，直接贴了。

int gcd(int a,int b){
   return b==0?a:gcd(b,a%b);
}

• 注意 \(gcd\) 只能处理正数，负数处理方法见线性同余方程。

• 顺带一提，\(lcm\)（最小公倍数） \(\times gcd = a\times b\)

题

luogu P1029

EXGCD

原理要用到 \(gcd\) ，但用处和 \(gcd\) 关联其实不是很大。

裴蜀定理

方程
\[ ax+by=gcd(a,b) \]
至少有一组整数解。

证明

不难看出问题可以简化成：
\[ ax+by=gcd(a,b) \iff mx+ny=1 \]
其中，\(m\)、\(n\) 为质数。即证明两个质数可以线性组合出 \(1\) 。

由 \(gcd\) 的过程我们发现，辗转相除的实质就是更相减损，即用两数加减组合。即两个质数可以组合出 \(1\) （也可以组合出 \(0\)）。

exgcd

根据裴蜀定理，我们知道，对于一个二元一次方程：
\[ ax+by=c \]
当 \(c\) 为 \(gcd(a,b)\) 的整数倍时，方程有整数解。

那么如何解这个方程呢？

原理

当 \(gcd(a,b)|c\) 时 ，我们将等式两边同除以 \(\frac{c}{gcd(a,b)}\)：
\[ ax+by=c \iff a\times \frac{x}{c}+b\times\frac{y}{c}=gcd(a,b) \]

设\(\frac{x}{c}\) 和 \(\frac{y}{c}\) 为 \(x'\) 和 \(y'\)，根据 \(gcd\) 的原理我们知道：
\[ b\times x''+a\%b \times y''= gcd(b,a\% b)\\implies b\times x''+(a-b\times \lfloor\frac{a}{b}\rfloor)\times y''=gcd(b,a\%b)\\implies a\times y''+b\times (x''-\lfloor\frac{a}{b}\rfloor\times y'')=gcd(b,a\%b)=gcd(a,b)\\implies a\times y''+b\times (x''-\lfloor\frac{a}{b}\rfloor\times y'')=ax'+by' \\therefore x'=y''\qquad y'=x''-\lfloor\frac{a}{b}\rfloor\times y'' \]
这样不断递归下去，直到：
\[ gcd(a,b)\times x'''+0\times y'''=gcd(a,b)\\therefore \ x'''=1\qquad y'''=0 \]
然后回溯回去求得 \(x\) 和 \(y\) 。

Code

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
    }
    else{
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
}

线性同余方程*

母题

求解
\[ ax \equiv b \ (mod \ p) \]
原式可以如下变换：
\[ (a\times x)\%p=b\%p \iff (a\times x-b)\%p=0\\implies ax+b=py \\ \implies ax+(-p)y=b \]
这样我们就能用 \(exgcd\) 求解了。

下面我们来上题

例题

luogu P1082 MOD

模板啦直接贴代码

#include<cstdio>
#include<algorithm>
using namespace std;

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
    }
    else{
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
}

int main()
{
    int a,b;
    int x,y;
    scanf("%d %d",&a,&b);
    //a,b互质 
    exgcd(a,b,x,y);
    printf("%d",((x%b)+b)%b);
    return 0;
}

[luogu P1516] 青蛙ha的约会

1. 题目大意：

求满足 \(x+k\times n \equiv y+k\times m \quad (mod \; l)\) 的最小的 \(k\) 。

1. 推柿子：

\[ (x+k\times n )\%l = (y+k\times m)\%l\\implies (x-y)+(n-m)\times k=l\times \lambda\\implies (m-n)\times k+l\times \lambda=x-y \]

然后几乎就转化成裸题辽。

1. 细节

我们发现 \(m-n\) 可能是负数，但是 \(exgcd\) 只能处理正数，所以要小小变换一下。因为我们只需要知道 \(k\) ，就可以这样：
\[ (m-n)\times k+l\times \lambda=x-y \iff (n-m)\times k+l\times (-\lambda)=y-x \]

1. \(Code\)

#include<cstdio>
#include<algorithm>
typedef int int_;
#define int long long
using namespace std;

int n,m,wa,wb,l;

int mod(int o,int p){
    return ((o%p)+p)%p;
}

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;y=0;
    }
    else{
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
}



int_ main()
{
    scanf("%lld %lld %lld %lld %lld",&wa,&wb,&n,&m,&l);
    wa=mod(wa,l);wb=mod(wb,l);
    int a=m-n,b=l,c=wa-wb;
    if(a<0){
        a=-a;
        c=-c;
    }
    int g=gcd(a,b);
    if(c%g != 0){
        printf("Impossible");
        return 0;
    }
    a/=g;b/=g;c/=g;
    int x,y;
    exgcd(a,b,x,y);
    x*=c;
    x=mod(x,b);
    printf("%lld",x);
    return 0;
}

[luogu P2421] 荒岛野人

1. 题目大意

和上题稍有不同，这题是两两求\(c_i+k\times p_i \equiv c_j+k\times p_j\quad (mod\; M)\) 在 \(min(l_i,l_j)\) 内无正整数解。

1. 做法

很简单，只需从小到大枚举\(M\) ，然后检验每两个人都不会相遇就ok。

#include<cstdio>
#include<algorithm>
using namespace std;
#define maxn 1000000

int n,maxx,c[20],p[20],l[20];

int mod(int o,int M){
    return ((o%M)+M)%M;
}

int gcd(int a,int b){
    return b==0?a:gcd(b,a%b);
}

void exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1,y=0;
    }
    else{
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
}

bool work(int i,int j,int m){
    int a=p[i]-p[j],b=m,d=c[j]-c[i];
    if(a<0){
        a=-a,d=-d;
    }
    int g=gcd(a,b);
    if(d%g != 0){
        return false;
    }
    a/=g,b/=g,d/=g;
    int x,y;
    exgcd(a,b,x,y);
    x*=d;
    x=mod(x,b);
    if(x <= min(l[i],l[j])) return true;
    else return false;
}

bool check(int m){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(work(i,j,m)){
                return false;
            }
        }
    }
    return true;
}




int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&c[i],&p[i],&l[i]);
        maxx=max(maxx,c[i]);
        c[i]--;
    }
    for(int i=1;i<=maxn;i++){
        if(check(i)){
            printf("%d",max(maxx,i));
            return 0;
        }
    }
    return 0;
}

• by thorn_

GCD 及 EXGCD 复习笔记

原文：https://www.cnblogs.com/thornblog/p/11715805.html