算法

扩展欧几里得算法

1. 扩展欧几里得
   用于求解方程 ax+by=gcd(a,b)ax+by=gcd(a,b) 的解

当 b=0b=0 时 ax+by=aax+by=a 故而 x=1,y=0x=1,y=0
当 b≠0b≠0 时

因为
gcd(a,b)=gcd(b,a%b)
gcd(a,b)=gcd(b,a%b)
而
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a%b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
bx′+(a−⌊a/b⌋∗b)y′=gcd(b,a%b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
ay′+b(x′−⌊a/b⌋∗y′)=gcd(b,a%b)=gcd(a,b)
故而

x=y′,y=x′−⌊a/b⌋∗y′
x=y′,y=x′−⌊a/b⌋∗y′
因此可以采取递归算法 先求出下一层的x′x′和y′y′ 再利用上述公式回代即可

1. 对于更一般的方程 ax+by=cax+by=c
   设 d=gcd(a,b)d=gcd(a,b) 则其有解当且仅当 d|cd|c
   求解方法如下:

用扩展欧几里得求出 ax0+by0=dax0+by0=d 的解

则a(x0∗c/d)+b(y0∗c/d)=ca(x0∗c/d)+b(y0∗c/d)=c
故而特解为 x′=x0∗c/d,y′=y0∗c/dx′=x0∗c/d,y′=y0∗c/d
而通解 = 特解 + 齐次解

而齐次解即为方程 ax+by=0ax+by=0的解

故而通解为 x=x′+k∗b/d,x=y′−k∗a/dk∈zx=x′+k∗b/d,x=y′−k∗a/dk∈z
3.应用: 求解一次同余方程 ax≡b(modm)ax≡b(modm)
则等价于求

ax=m∗(−y)+b
ax=m∗(−y)+b
ax+my=b
ax+my=b

有解条件为 gcd(a,m)|bgcd(a,m)|b,然后用扩展欧几里得求解即可

特别的 当 b=1b=1 且 aa与mm互质时 则所求的xx即为aa的逆元

// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1; y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= (a/b) * x;
    return d;
}

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
int main(){
    int n,a,b,x,y;
    cin>>n;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

----------