扩展欧几里得

约 289 个字 12 行代码 预计阅读时间 1 分钟

exgcd

该算法要解决的问题

求解线性同余方程（又称模线性方程）

线性指未知数都是一次的方程

最基本的同余方程，

即$ax\equiv b \pmod n$，其中$a$、$b$、$n$都为常量，x是未知数，

原理

上述方程可以进行一定的转化，

得到：$ax = kn + b$,这里的k为任意整数，

于是我们可以得到更加一般的形式即：$ax + by + c = 0$，

这个方程就是二维空间中的直线方程，

但是$x$和$y$的取值为整数，所以这个方程的解是一些排列成直线的点集。

有解充分必要条件

设$d=gcd(a,b)$

若$c\%d=0$,则方程有解

例如$2*x+4*y=1$没有整数解，因为gcd=2，1%2=1

根的形式

$x=x_0+Bk/d,y=y_0-Ak/d$(k是任意整数,/是整除,$x_0$和$y_0$是特解)

若c是gcd的倍数,x和y乘相应的倍数即可

代码

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1;
        y=0;
        return a;
    }
    int r=exgcd(b,a%b,y,x);
    y-=x*(a/b);
    return r;
}

注意：

exgcd函数返回值是最大公约数,调用后引用的x和y赋值为特解

如需求X正整数最小解

加上以下代码

    int t=B/d;
    ans=(C/d*x%t+t)%t;