基础用法

给定 $ n $ 对正整数 $ a_i, b_i $，对于每对数，求出一组 $ x_i, y_i $，使其满足 $ a_i \times x_i + b_i \times y_i = gcd(a_i, b_i) $。

裴蜀定理

对于任意正整数\(a, b\)，那么一定存在非零整数\(x,y\)使得\(ax + by = gcd(a , b )\)

假设\(ax + by = d\)，那么\(d\)一定要是\(gcd(a,b)\)的倍数

显然，\(a,b,ax,by,ax+by\)都是\(gcd(a,b)\)的倍数，因此\(d = ax+by\)是\(gcd(a,b)\)的倍数

因此\(d\)最小是一倍的\(gcd(a,b)\)，也就是\(d=gcd(a,b)\)

所以这个方程\(ax + by = d\)最小的解便是\(gcd(a,b)\)

因此题中的方程一定有解

这个解就由扩展欧几里得算法解出

想法

先回顾欧几里得算法：

if(!b)
{
    return a;
}
return gcd(b, a % b);

\(1.\) 先看if(!b)的情况，当\(b=0\)时，\(gcd(a,b)=gcd(a,0)=a\)

代入原式中，\(a\times x + 0 \times y= a\)

解得\(x = 1, y = 0\)

\(2.\) if(b)时，用int d记录exgcd(b, a % b, y, x)

由于此处颠倒了\(a,b\)的顺序，因此传入\(x,y\)时也要颠倒

\[原式 = by + (a\%b)x = d \]

此处\(a\%b = a - \lfloor \frac{a}{b}\rfloor \times b\)

由于$a\div b = \lfloor \frac{a}{b}\rfloor \dots a%b $

所以\(a\%b = a - \lfloor \frac{a}{b}\rfloor \times b\)

因此

\[by+(a - \lfloor \frac{a}{b}\rfloor \times b)x =d \]

把\(x\)乘进去，得：

\[ax + b(y- \lfloor \frac ab\rfloor x) =d \]

码来！

#include <iostream>
using namespace std;

int Extended_Euclidean(int a, int b, int &x, int &y) // 记得加引用
{
    if(!b)
    {
        x = 1;
        y = 0;
        return a;
    }
    
    int d = Extended_Euclidean(b, a % b, y, x); // 颠倒
    
    y = y - a / b * x; // 套公式
    return d; // 返回gcd(a, b)
}

int main()
{
    int n;
    int a, b, x, y;
    scanf("%d", &n);
    while (n -- )
    {
        scanf("%d%d", &a, &b);
        
        Extended_Euclidean(a, b, x, y); // 算法写全名会不会霸气一点 []~(￣▽￣)~*
        
        printf("%d %d\n", x, y);
    }
    return 0;
}

扩展欧几里得算法求逆元

我们已知当\(p\)是质数的时候，可以用快速幂算法求逆元

详见这篇博客

那么，当\(p\)不是质数的时候，用什么呢？

答案是：扩展欧几里得算法

\(a\)有逆元的充分必要条件是\(a\)与\(p\)互质，因此\(gcd(a, p) = 1\)
所以设逆元为\(x\)，则\(a * x \equiv 1 \bmod p\)
则\(ax + py = 1\)
那么exgcd(a, p, x, y)就能算出来

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;

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; // 返回gcd(a, b)
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int x, y, a, p;
        cin >> a >> p;
        int d = exgcd(a, p, x, y);
        if(d == 1) // 有解
        {
            cout << ((LL)x + p) % p << endl; // 保证正数
        }
        else puts("impossible");
    }
    return 0;
}

感谢观看~