$$\Huge 扩展欧几里得算法$$

问题

$给定a , b$

$求ax + by = gcd(a, b)的一组解$

$扩展欧几里得算法$

$通过欧几里得算法,gcd(a, b) = gcd(b, a \% b)$

$先计算关于x’ , y’的方程 bx’ + (a % b)y’ = gcd(a, b)$

$由于a \% b = a - \left \lfloor \frac{a}{b} \right \rfloor * b$

$那么将原式简化成$

$$bx’ + (a - \left \lfloor \frac{a}{b} \right \rfloor * b) y’ = gcd(a, b)$$

$$bx’ + ay’ - \left \lfloor \frac{a}{b} \right \rfloor * b * y’ = gcd(a, b)$$

$$ay’ + b(x’ - \left \lfloor \frac{a}{b} \right \rfloor * y’) = gcd(a, b)$$

$所以只要解出方程bx’ + (a \% b)y’ = gcd(a, b)的解x’, y’$

$那么原方程的解x = y’ , y = x’ - \left \lfloor \frac{a}{b} \right \rfloor * y’$

$Code$

int exgcd(int a, int b, int &x, int &y)//x,y表示答案
{
    if (b == 0)//已经算出了gcd(a,b)
    {
        x = 1, y = 0;//变形为ax = a 的形式,得出答案
        return a;//返回gcd(a,b)的值
    }

    int d = g(b, a % b, y, x);//交换x,y的位置,更方便的进行转换
    y -= a / b * x;

    return d;
}

$答案转换$

一般形式

$在欧几里得算法的应用中$

$通常运用ax + by = c这样的方程$

$由于gcd(a,b) | a 并且 gcd(a, b) | b$

$所以 c 一定是 gcd(a,b) 的 倍数$

$若不是,则无解$

$若ax_0 + by_0 = gcd(a,b)$

$那么 a \frac{x_0c}{gcd(a,b)} + b \frac{y_0c}{gcd(a,b)} = c$

$所以方程的一组解为x = \frac{x_0c}{gcd(a,b)},y = \frac{y_0c}{gcd(a,b)}$

最小解

$求ax+by=c方程中x的最小解$

$$ax + by = c$$

$$ax + by + abk - abk = c$$

$$a(x - bk) + b(y + ak) = c$$

$即 (x \% b + b) \% b 是最小解$