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

什么叫扩展欧几里得?简易的说,便是求有关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,得:

    a1x b1y = 1

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

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

    gcd(a1, b1) = gcd(b1, r1) = gcd(r1, r2) = …… = gcd(rn-1, rn) = 1

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

    • a1 = x1b r1

    • b1 = x2r1 r2

    • r1 = x3r2 r3

      ……

    • rn-3 = xn-1rn-2 rn-1

    • rn-2 = xnrn-1 rn

    • rn-1 = xn 1rn

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

    • rn-2 = xnrn-1 1 ---> 1 = rn-2 - xnrn-1

    由到数第三行得:rn-1 = rn-3 - xn-1rn-2带到上式

    得:1 = (1 xnxn-1)rn-2 - xnrn-3

    采用一样的方式 ,逐一消除rn-2,……, r1

    最后会获得1 = f(x)a1 g(x)b1

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

    设f(x) = x, g(x) = y,则能够获得1 = a1x b1y, 得证!

    平常人都讨厌看上边写的稀奇古怪的计算,那么就看下面我这个实际的计算叭,这儿是假定到 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时才有解,根据拓展欧几里得优化算法获得的解x0,运用x0%p就可以获得最少解

为什么呢?

由于通解为x = x0 p * k

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

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

当 p 是负值的情况下,大家取 p 的平方根就可以了,当 x0 是负值的情况下,x0% p 的結果依然是负值(在电子计算机测算的結果上是那样的,尽管界定的情况下不是这样的),此刻,大家依然让 x0 对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;
}

评论(0条)

龙8唯一官方网站 游客评论