探讨拓展欧几里得优化算法

什么叫扩展欧几里得？简易的说，便是求有关x,y的方程组 ax by = gcd(a,b) 的全部整数金额解

如今大家来处理四个难题

• 什么叫裴属定律，怎样证实裴属定律？

• 如何使用拓展欧几里得去求ax by = gcd(a,b) 的特解？

• 怎么求由特解发布别的的全部解？

• 拓展欧几里得的三大运用

一、裴蜀定理內容即证实

內容

设a, b不是全为零的整数金额，则存有整数金额x, y 促使 ax by = gcd(a, b).

证实：

1. a, b中倘若有一个为0，则以上定律彻底符合，如a = 0, 则gcd(a, b) = b , 显而易见创立

2. 若a, b 都并不等于0

   设gcd(a, b) = d,则d != 0

   式子两侧另外除于d，得：

   a₁x b₁y = 1

   再运用辗转相除法：gcd(a, b) --> gcd(b, a % b) --> ……

   设模出去的余数称为x, 则有：

   gcd(a₁, b₁) = gcd(b₁, r₁) = gcd(r₁, r₂) = …… = gcd(r_n-1, r_n) = 1

   把辗转相除法中的计算进行，制成带余数的除法，得

   • a₁ = x₁b r₁

   • b₁ = x₂r₁ r₂

   • r₁ = x₃r₂ r₃

     ……

   • r_n-3 = x_n-1r_n-2 r_n-1

   • r_n-2 = x_nr_n-1 r_n

   • r_n-1 = x_{n 1}r_n

   何不令辗转相除法在除到互质的情况下撤出则 r_n = 1 , 由到数第二行得

   • r_n-2 = x_nr_n-1 1 ---> 1 = r_n-2 - x_nr_n-1

   由到数第三行得：r_n-1 = r_n-3 - x_n-1r_n-2带到上式

   得：1 = (1 x_nx_n-1)r_n-2 - x_nr_n-3

   采用一样的方式 ，逐一消除r_n-2,……, r₁

   最后会获得1 = f(x)a₁ g(x)b₁

   在其中f(x)和g(x) 是有关x的涵数

   设f(x) = x, g(x) = y，则能够获得1 = a₁x b₁y, 得证!

   平常人都讨厌看上边写的稀奇古怪的计算，那么就看下面我这个实际的计算叭，这儿是假定到 r4 = 1，随后向前计算滴

   

二、求特解

大家都了解，欧几里得公式计算能够由这一算式表述

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

根据这一算式，我们可以持续递推到b = 0， 这时a即是a和b的最大公约数

如今大家对这一算式开展进行，看一下有什么好玩的嘛

gcd(a, b) = a * x1 b * x2

gcd(b, a % b) = b * x2 (a % b) * y2

在其中a % b = a - (a / b) * b

故由第一行的欧几里得公式计算得：

a * x1 b * y1 = b * x2 {a - (a / b) * b}y2

化简得a * x1 b * y1 = a * y2 b * {x2 - (a / b) * y2}

依据待定系数法获得

• x1 = y2

• y1 = x2 - (a / b) * y2

换句话说，假如拥有gcd(b, a % b)的解x2, y2就可以发布gcd(a, b)的解x1, y1

那麼这就和求gcd的全过程一样，一直推倒最终x = 1， y = 0，就可以回朔回来，获得gcd(a, b)的特解x1, y1

特解实际上是最少的一个解

二、如何运用特解发布别的全部整数金额解

先说结果：

\[x = x0 k * \frac{b}{gcd(a,b)} \]

\[y = y0 - k * \frac{a}{gcd(a,b)} \]

随意的x y = x0 y0

x0, y0便是方程组的特解

针对a * x b * y = g而言，让x提升b/gcd,让y提升a / gcd

那样就等同于加a * b / gcd，减掉a * b / gcd,一加一减，最后不会改变

三、拓展欧几里得三大运用

• 用拓展欧几里得优化算法解不定方程ax by=c

假如 c % gcd(a, b) == 0，即c 是 gcd(a, b)的非负整数，则方程组有解，且解就在上面的基本上品以$$\frac{c}{gcd(a, b)}$$就可以

void e_gcd(int a, int b, int &gcd, int &x, int &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        gcd = a;
    }
    else
    {
        e_gcd(b, a % b, gcd, y, x);
        y -= x * (a / b);
    }
}

int main(){
    int a, b, x, y, gcd;
  	cin>>a>>b;
    e_gcd(a, b, gcd, x, y);
    cout<<x<<' '<<y<<endl;
    cout<<gcd<<endl;
    return 0;
}

• 用拓展欧几里得优化算法求得模线性方程ax≡b (mod n)

  针对模线性方程ax≡b (mod n)能够化简为ax ny = b，设d = gcd(a, n) 当且仅当b % d == 0时有解，且有d个解

  当b % d == 0时，设ax ny = d,的特解为x,y

  式子两侧另外乘于\(\frac{b}{d}\)，则方程组变为\(ax\frac{b}{d} ny\frac{b}{d} = b\)

  则原方程组ax ny = b的解得\(x' = x*\frac{b}{d},y' = y*\frac{b}{d}\)

  故ax≡b (mod n)的特解为 x0 = x * (b / d) % n

  d个解得xi= x0 i*(n/d) mod n，{i = 0……n-1}

  解的间距为n/d

void exgcd(int a, int b, int &gcd, int &x, int &y)
{
    if (b == 0){
        x = 1;
        y = 0;
        gcd = a;
    }
    else{
        exgcd(b, a % b, gcd, y, x);
        y -= x * (a / b);
    }
}

bool modular_linear_equation(int a, int b, int n){
    int x, y, x0, gcd;
    exgcd(a, n, gcd, x, y);
    int d = gcd;//d为gcd(a, n)
    if(b % d)return false;//难解
    x0 = x * (b/d) % n;//特解
    for(int i = 0; i < d;   i)cout<<x0   i * (n / d)<<endl;//全部的解
    return true;
}

• 用欧几里德优化算法求乘法逆元：

什么是乘法逆元？

ax ≡ 1 (mod p)

这儿大家称x为a有关p的逆元

以上算式能够复原为：ax py = 1,依据上边讲的拓展欧几里得优化算法，我们知道gcd(a, p) = 1时才有解，根据拓展欧几里得优化算法获得的解x₀,运用x₀%p就可以获得最少解

为什么呢？

由于通解为x = x₀ p * k

那麼，换句话说， a 有关 p 的逆元是一个有关 p 同余的，那麼依据最少整数金额基本原理，一定存有一个最少的整数，它是 a 有关p 的逆元，而最少的毫无疑问是在（0 , p）中间的，并且只有一个，这就行表述了。

可是，因为难题的独特性，有时大家获得的特解 x₀ 是一个负值，也有的情况下大家的 p 也是一个负值这该怎么办？

当 p 是负值的情况下，大家取 p 的平方根就可以了，当 x₀ 是负值的情况下，x₀% p 的結果依然是负值（在电子计算机测算的結果上是那样的，尽管界定的情况下不是这样的），此刻，大家依然让 x₀ 对abs(p) 牙模型，随后結果再再加上abs(p) 就可以了，因此，大家不会太难写下下边的编码求得一个数 a 针对另一个数 p 的乘法逆元：

int a, b, x, y, gcd, ans, p;

void exgcd(int a, int b, int &gcd, int &x, int &y)
{
    if (b == 0){
        x = 1;
        y = 0;
        gcd = a;
    }
    else{
        exgcd(b, a % b, gcd, y, x);
        y -= x * (a / b);
    }
}

inline int cal(int a, int p){
    exgcd(a, p, gcd, x, y);
    if(1 % gcd != 0)return -1;
    x = x * 1 / gcd;
    p = abs(p);
    ans = x % p;
    if(ans <= 0)ans  = p;
    return ans;
}