拓展欧几里得-求解线性同余方程

拓展欧几里得

欧几里得算法

原理

辗转相除法：用$a$除以$b$，得到余数$r$和结果$q$，再用除数$b$除以余数$r$得到新余数$r2$，再用除数$r$除以$r2...$直至余数为0此时的除数即为最大公因数。

辗转相除法的依据：

$gcd(a,b)=gcd(b,a\%b)$

应用

求两个数的最大公约数。

拓展欧几里得

裴属定理

1 1​cpp

$a_0x_0+b_0y_0=gcd(a_0,b_0)$

即如果$ax+by=m$有解，那么$m$一定是$gcd(a,b)$的整数倍。

解释

联系辗转相除法的依据，我们可以得到：

$b_0x_1+(a_0\%b_0)y_1=gcd(a_0,b_0)=gcd(b_0,b_0\%a_0)$

$a_1=b_0，b_1=a_0\%b_0$

当除数为0时，被除数为最大公约数此时$x_n=1,y_n=0$，之后我们可以一层层往前推出$x_0,y_0$。

$x_i=y_{i+1}$

$y_i=x_{i+1}-(a_{i}/b_{i})*y_{i+1}$

示例代码

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

求解线性同余方程

定义

形如

$ax\equiv n\pmod b$

的方程称为线性同余方程。其中$a,b,n$为给定整数，$x$为未知数。

扩展欧几里得求解

$ax\equiv n\pmod b$等价于$ax+by=n$，此方程有整数解的充要条件是$n \% gcd(a,b)==0$(裴属定理)。

我们可以通过扩展欧几里得求得一组解($n=gcd(a,b)$时)$x_0,y_0$。

此时可以得到：

$x=\frac{x_0*n}{gcd(a,b)}$

此特解加上$r=\frac{b}{gcd(a,b)} $的整数倍再模$b$即为通解。

最小正整数解为：

$x_{min}=(x\%r+r)\%r$

示例代码

void Equation(int a, int b, int n)
{
    int x, y;
    int d = ex_gcd(a, b, x, y);
    if (n % d != 0)
        return;
    x = x * n / d;
    int r = b / d;
    for (int i = 0; i < d; i++)
    {
        printf("%d\n", (x + i * r) % b);
    }
}