拓展欧几里得算法思路解释、代码以及例题【线性同余方程】

 引入裴蜀定理：

有任意一对正整数a、b，一定存在非零整数x、y，使得a*x+b*y=gcd(a,b)，且gcd(a,b)是a、b添加系数后凑出来的最小正整数。

证明一下：

假设a*x+b*y=d

则需要证明的是：d是gcd(a,b)的倍数

因为a是gcd(a,b)的倍数，b是gcd(a,b)的倍数，

则 a*x+b*y也是gcd(a,b)的倍数

所以我们求的gcd(a,b)是a、b添加系数后凑出来的最小正整数。

那我们想证明一定存在的话，就是我们要接下来要说的拓展欧几里得算法了。

拓展欧几里得算法是为了算出这样的一组x，y。

题目链接：877. 扩展欧几里得算法 - AcWing题库

题面：

 

采用递归的思路来求解：

当b==0时，任何数与0的最大公约数都是它本身。

当b==0时，a*x+0*y=a要成立的话，一组解为x=1,y=0;

其他的情况就是一直递归：

int d=exgcd(b,a%b,y,x)，这里可以注意到这里传入的数值顺序改变了，读者自行理解一下

我们就有了这个式子：gcd(a,b)=gcd(b*y+a%b*x)

而a%b=a-a/b*b    (a/b注意向下取整)

展开右边有：d=b*y+a*x-a/b*x

                       =a*x+b(y-a/b*x)

                即

                y=y-a/b*x;

                x=x;

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
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=y-a/b*x;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    while(n--)
    {
        int a,b,x,y;
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" " <<y<<endl;
    }
    return 0;
}

拓展欧几里得算法例题：

题目链接：878. 线性同余方程 - AcWing题库

题面：

 

思路：

题目要求的是满足 ai × xi ≡ bi (mod mi)的xi。

举个例子a=4,b=3,m=5时，4 * x % 5 = 3 % 5, x = 2 或 -3 (2,-3互余于5)

由此我们只需要找出a * x % m = b

[所以存在一个正整数y ，使得上式等价变形为] a * x = y * m + b

 a * x - y * m = b

有上面的拓展欧几里得算法解释，我们可以知道，b一定是gcd(a,b)的倍数，否者不存在x

如果是倍数的话，x可以表示为x*（ b / gcd(a,b) ） % m。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10;
const int mod=1e9+7;
//拓展欧几里得算法模板
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=y-a/b*x;
    return d;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin>>n;
    while(n--)
    {
        int a,b,m;
        cin>>a>>b>>m;
        int x,y;
        int d=exgcd(a,m,x,y);//求出来了a,b的最大公约数
        if(b%d!=0)//即b不是gcd（a,b）的倍数
            cout<<"impossible"<<endl;
        else cout<<(ll)x*(b/d)%m<<endl;
    }
    return 0;
}