zcmimi's blog

转自https://www.cnblogs.com/hadilo/p/5914302.html

欧几里得

定义:

gcd(a,b)为整数ab的最大公约数

引理:

gcd(a,b)=gcd(b,a \bmod b)

证明:

r=a \bmod b , c=gcd(a,b)

a=xc,b=yc, 其中x,y互质

r=a \bmod b=a-pb=xc-pyc=(x-py)c

b=yc

可知:yx-py互质

证明:

假设yx-py不互质

y=nk,x-py=mk, 且k>1(因为互质)

y带入可得

x-pnk=mk

x=(pn+m)k

a=xc=(pn+m)kc,b=yc=nkc

那么此时ab的最大公约数为kc不为k

与原命题矛盾,则yx-py互质

因为yx-py互质,所以rb的最大公约数为c

gcd(b,r)=c=gcd(a,b)

得证

a\mod b=0时,gcd(a,b)=b

这样我们可以写成递归形式

实现:

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

扩展欧几里得

引理:

存在x,y 使得gcd(a,b)=ax+by

证明:

b=0 时,gcd(a,b)=a,此时 x=1 , y=0b \neq 0 时,设

ax+by=gcd(a,b)=gcd(b,a \bmod b)=b{x}'+(a \bmod b){y}'

\because a \bmod b = a-a/b*b

\therefore ax+by=b{x}'+(a-a/b*b){y}'

\therefore ax+by=b{x}'+a{y}'-b*a/b*{y}'

\therefore ax+by=a{y}'+b{x}'-b*a/b*{y}'

\therefore ax+by=a{y}'+b({x}'-a/b*{y}')

解得 x={y}' , y={x}'-a/b*{y}'

b=0时存在x,y为最后一组解

实现:

递归进入下一层,当b=0时就返回x=1,y=0

再根据x=y' , y={x}'-a/b*y'得出当前所在层的解

回到第一层的时候得到答案。

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

LG 1082 同余方程

求关于x的同余方程ax \equiv 1 \pmod b的最小正整数解。

ax \equiv 1 \pmod b可以转化为ax+by=1

方程ax + by = m有解的必要条件是m \mod \gcd(a,b) = 0

\therefore \gcd(a,b) = 1,即a,b互质

用扩展欧几里得求ax+by=\gcd(a,b)的解即可

我们求出来的x必然满足方程,但是不一定是最小正整数解

ax+by=1

ax+by+k\times ba-k\times ba=1

a(x+kb)+(y-ka)b=1

所以x+=bx-=b不会使x错过任何解

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll x,y;
void exgcd(ll a,ll b){
    if(!b){
        x=1,y=0;
        return;
    }
    exgcd(b,a%b);
    int t=x;
    x=y;
    y=t-a/b*y;
}
int main(){
    ll a,b;
    cin>>a>>b;
    exgcd(a,b);
    while(x<0)x+=b;
    x%=b;
    cout<<x<<endl;
}

作者:zcmimi

链接:https://blog.zcmimi.top/posts/exgcd/

声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0许可协议. 转载请注明来自zcmimi's blog

exgcd
comment评论
Search
search