目录

• 欧几里得算法
• 裴蜀定理
• 扩展欧几里得算法
• 线性同余方程

欧几里得算法

欧几里得算法，即辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
核心原理：gcd(a,b) = gcd(b,a mod b)
一个基本的性质：d | a，d | b，d | (a+b)，d | (ax + by)
（d能整除a，d能整除b，那么d就能整除a+b，也能整除a的若干倍+b的若干倍）

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

b不为0时，最大公约数是gcd(b, a mod b)
b为0时，最大公约数就是a（0可以整除任何数）

裴蜀定理

在学习扩展欧几里得算法之前，先来简单了解一下裴蜀定理
内容：对于任意正整数a，b，那么一定存在非零整数x，y，使得
ax + by = (a,b) （a和b的最大公约数）
ax + by = d （d为a和b的最大公约数的倍数）
显然，凡是能由a和b凑出来的数，一定是a和b最大公约数的倍数，而其中最小的正整数就是a和b的最大公约数。
而扩展欧几里得是一个算法，它能够在已知任意正整数a和b的前提下，都可以求出符合上述条件的x，y。

扩展欧几里得算法

给定 n 对正整数 ai,bi，对于每对数，求出一组 xi,yi，使其满足 ai×xi+bi×yi=gcd(ai,bi)。
思路：
1.当 b = 0 时，a和b的最大公约数就是a，所以有ax + 0y = a，显然 x = 1，y = 0 就是一组解

2.当 b ≠ 0 时，
已知 ，gcd(a，b) = gcd(b，a % b)
递归结束后，就有 by + (a mod b)x = (a,b) = d
a mod b = a - ⌊a/b⌋·b

by + (a % b)x = gcd(b，a % b)

by + (a - ⌊a / b⌋ * b)x = gcd(b，a % b)

ax+ b(y- ⌊a / b⌋ * x) = gcd(b，a % b) = gcd(a，b) = ax + by

所以，x = x ，y = y - ⌊a / b⌋ * x

#include <iostream>

using namespace std;

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);
    //b和a%b的系数分别为y和x
    
    y -= a/b * x;
    
    return d;
}
int main()
{
    int n;
    scanf("%d",&n);
    
    while(n -- )
    {
        int a,b,x,y;
        scanf("%d %d",&a,&b);
        
        exgcd(a,b,x,y);
        
        printf("%d %d\n",x,y);
    }
}

线性同余方程

给定 n 组数据 a_i,b_i,m_i，对于每组数求出一个 x_i，使其满足 a_i×x_i≡b_i(mod m_i)，如果无解则输出 impossible。
考点：扩展欧几里得算法的应用
分析：
a×x≡b(mod m) 等价于 存在一个整数y 使得 ax = my + b，即 ax - my = b，
ax + my^’ = b （y^’ = -y），这样就转换成了扩展欧几里得算法能够求解的形式，由扩展欧几里得算法可以求出 ax + my = gcd(a，b) 的解，那么怎么 ax + my = b 的解呢，很简单ax + my = gcd(a，b) 等式两边同乘 b / gcd(a，b) 即可前面提到过，此方程有解的充要条件是 (a,m) | b

#include <iostream>

using namespace std;

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);
    //b和a%b的系数分别为y和x
    
    y -= a/b * x;
    
    return d;
}
int main()
{
    int n;
    scanf("%d",&n);
    
    while(n -- )
    {
        int a,b,m;
        scanf("%d %d %d",&a,&b,&m);
        int x,y;
        int d = exgcd(a,m,x,y);
        
        if(b % d) puts("impossible"); //b不是(a,b)的倍数
        else
        printf("%d\n",(long long)x * b/d % m);
    }
    
    return 0;
}