基础用法

给定 $ 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;
}

感谢观看~