1. 拓展欧几里得

拓展欧几里得算法用于求解$ax+by=gcd(a,b)$的解

① 当$b=0$时，$ax+by=0$，故$x=1,y=0$

② 当$b≠0$时

因为$gcd(a,b)=gcd(b,a$%$b)$

而$bx′+(a$%$b)y=gcd(b,a$%$b)$

$\Rightarrow bx’+(a−⌊a/b⌋×b)y’=gcd(b,a$%$b)$

$\Rightarrow ay′+b(x′−⌊a/b⌋∗y’)=gcd(b,a$%$b)=gcd(a,b)$

综上：

$x=y’,y=x’−⌊a/b⌋∗y’$

#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y){//返回gcd(a,b) 并求出解(引用带回)
    if(b==0){
        x = 1, y = 0;
        return a;
    }
    int x1,y1,gcd;
    gcd = exgcd(b, a%b, x1, y1);
    x = y1, y = x1 - a/b*y1;
    return gcd; 
}
int main(){
    int n,a,b,x,y;
    cin>>n;
    while(n--){
        cin>>a>>b;
        exgcd(a,b,x,y);
        cout<<x<<" "<<y<<endl;
    }
    return 0;
}

$\\ $

2. 求解更一般的方程$ax+by=c$

设$d=gcd(a,b)$，则其有解当前仅当$d|c$(裴蜀定理)，求解：

① 求特解

由拓展欧几里得定理求出$ax_0+by_0=d(d=gcd(a,b))$的解，整理得：

$$a(x_0×c/d)+b(y_0×c/d)=c$$

则方程$ax+by=c$的一个特解为：$x’=x_0×c/d$、$y’=y_0×c/d$

② 求齐次解

齐次解即$ax+by=0$的解，求解如下：

整理出$x=-\frac{b}{a}y$，因为$gcd(a,b)=d$，所以$a=a_1×d,\ b=b_1×d$且$a_1$、$a_2$互质(假设不互质，则可以继续提公约数给$d$

那么$x$可以写成：$x=-\frac{b_1×d}{a_1×d}y=-\frac{b_1}{a_1}y$

因为$x$有整数解，所以$a_1|y$，即$y=ka_1(k∈Z)\ \Rightarrow\ y=k\frac{a}{d}\ ,x=-k×\frac{b}{d}$

③ 通解 = 特解+齐次解

$ax+by=c$的通解为：$x=x’-k×\frac{b}{d}, y=y’+k\frac{a}{d}$

$\ $

3. 求解同余方程$ax≡b(mod\ m)$

等价于求：$ax=m×(-y)+b \Rightarrow ax+my=b(mod \ m)$
有解条件为$gcd(a,m)|b$，然后利用拓展欧几里得算法求解即可
$\\ $

#include<bits/stdc++.h>
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 -= 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");
        else printf("%d\n", (ll)b / d * x % m); //b最大2e9，所以在/d*x后可能爆int所以要先转化成ll
    }
    return 0;
}