佩苏定理 + 欧几里得定理的扩展及其应用

今天算法课老师讲了扩展gcd，就好好学了下

裴蜀定理

对于任意一对正整数a,b，一定存在非零整数x,y使得ax+by=(a,b)，其中(a,b)为a和b的最大公约数。

裴蜀定理的常见应用和推论

1. 可以用来判断方程ax+by=c是否有解，只要看c是否是(a,b)的倍数

2.如果z是a和b的最大公约数(a,b)的整数倍，则一定存在x,y使得ax+by=z

扩展欧几里得算法的应用

用于求解方程 \(ax+by=gcd(a,b) 的解\)

扩展欧几里得的手写版理解与手算推导递归实现的扩展GCD

核心代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int exgcd(int a,int b,int &x,int &y)
{
    if (!b)
    {
        x=1,y=0;
        return a;
    }
    int x1,y1,d;
    d = exgcd(b,a%b,x1,y1);
    x = y1, y = x1-a/b*y1;
    return d;
}
int main()
{
    scanf("%d",&n);
    while (n--)
    {
        int a,b,x,y;
        scanf("%d%d",&a,&b);
        int d = exgcd(a,b,x,y);
        printf("%d %d\n",x,y);
    }
    return 0;
}