拓欧

扩展欧几里得

辗转相除法可以来求a，b两个数的最大公约数。而辗转相除的过程中，附带也可以得到满足ax+by=c(△)ax+by=c(△)的解系(X,Y)(X,Y)

先来解决ax+by=gcd(a,b)(∗)ax+by=gcd(a,b)(∗)这一特殊情况。

最简情况：b=0b=0时，gcd(a,b)=agcd(a,b)=a，方程化为ax=aax=a,则一组特殊解为(1,0)(1,0)
当b≠0b≠0时，由辗转相除法gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a%b)可以改写原方程得到
bx′+(a%b)y′=gcd(b,a%b)bx′+(a%b)y′=gcd(b,a%b)又a%b=a−⌊ab⌋×ba%b=a−⌊ab⌋×b，代入前一方程，得到
ay′+b(x′−⌊ab⌋y′)=gcd(a,b)ay′+b(x′−⌊ab⌋y′)=gcd(a,b)与方程(*)对比ax+by=gcd(a,b)ax+by=gcd(a,b)，可知：x=y′，y=(x′−⌊ab⌋y′)x=y′，y=(x′−⌊ab⌋y′)得到一组递推关系。
方程依次向下递归可以得到最简情况，得到解（1，0），再由递推关系回代到上一组解，最终可以得到方程（*）的解。注意到，这是一组特解，并不唯一。

//解方程ax+by=gcd(a,b) 返回gcd(a,b) 得到一组特解(x,y)
int extend_Euclid(int a, int b, int &x, int &y){
    if(b==0){
    x = 1; y = 0;
    return a;
    }
    int r = extend_Euclid(b, a%b, y, x);
    y -= a/b*x;
    return r;
}

解二元一次线性方程

//求解ax+by=c 返回0为无解,否则返回gcd(a,b)个解,用X[],Y[]存;
int X[N], Y[N];
int equation(int a, int b, int c)
{
    int x, y;
    int g = extend_Euclid(a, b, x, y);
    if(c % g)
        return 0;    //表示无解
    x *= c/g, y *= c/g;
    for(int k = 0;k < g;k++)
    {
        X[k] = (x+b/g*k)%b;//b/g为x的循环节   加
        Y[k] = (c-a*X[k])/b;//a/g为y的循环节  减
    }
    return g;
}

求逆元

特别地，当有 $(a, m) = 1 时， a x \equiv 1 (\mod m)$