扩展欧几里得算法


扩展欧几里得算法


最大公约数

    欧几里得算法即辗转相除法,可以用来求两个数的最大公约数。
代码实现也很简单,如下:

typedef long long ll;
ll gcd(ll a, ll b)
{
    while(b)
    {
        ll temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

扩展欧几里得算法

    而扩展欧几里得算法,常用来求 ax + by = gcd(a, b) 中x,y的一组整数解。首先 ax + by = gcd(a, b) 是一个不定方程,其有整数解是一定的,而且有无穷多组整数解。因为我们只要找到了一组整数解,其他的解都可以写出。假设我们求出一组整数解$$x_{0}$$, $$y_{0}$$。则其通解即为:
x = $$x_{0}$$ + $$\frac{kb}{gcd(a, b)}$$,
y = $$y_{0}$$ - $$\frac{ka}{gcd(a, b)}$$, 其中k$$\in$$Z.
至于为什么一定有整数解嘛,我是不会证明。可以看 OI Wiki 上面有该方程整数解的求法过程,既然人家都已经求出来了,还谈什么到底有没有整数解干嘛...肯定有啊!
下面是扩展欧几里得算法的递归实现:

typedef long long ll;
//传入的x, y指针返回一组特解
ll exGcd(ll a, ll b, ll *x, ll *y)
{
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }
    ll res = exGcd(b, a % b, x, y);
    ll temp = *x;
    *x = *y;
    *y = temp - a / b * (*y);
    return res; //返回值为 gcd(a, b)
}

例题

    如果只是看了扩展欧几里得的知识点肯定是云里雾里,不知道有什么用。对于我这种渣渣来说那就只能从相关的题目中领悟其真谛了。
看一道模板题,洛谷P1082, 点我传送看题
题解: 题目要我们求关于x 的同余方程 ax $$\equiv$$ 1 (mod b),中x的最小正整数解。
这个式子可以转化为二元方程ax = bk + 1其中k$$\in$$Z.
再把bk调到左边来,就变成了ax - bk = 1.
这个式子是不是和扩展欧几里得那个有点像啊?我们再令 -k = y,
这个式子是不是变成了ax + by = 1,最后我要说的是如果gcd(a, b) = 1则存在整数解,否则就不存在。
而这题已经说了一定有解,所以gcd(a, b)一定是等于1的。
到最后我们发现,这就是扩展欧几里得那个式子。所以套一下模板就出来了。
下面是AC代码:

//洛谷P1082 同余方程
#include <stdio.h>
int exGcd(int a, int b, int *x, int *y)
{
    if(b == 0){
        *x = 1;
        *y = 0; //y 据说可取任意值,取0是为了好算
        return a;
    }
    int res = exGcd(b, a % b, x, y);
    int temp = *x;
    *x = *y;
    *y = temp - a / b * (*y);
    return res; 
}
int main(void)
{
    int a, b, x, y;
    scanf("%d%d", &a, &b);
    exGcd(a, b, &x, &y);
    x = (x % b + b) % b;    //将特解转换为最小非负整数解
    if(x == 0)  x += b; //如果x为0,则加上b,因为题目要求x为最小正整数解
    printf("%d\n", x);
    return 0;
}

    再来一个题,这个题要花更多步骤才能到扩展欧几里得那个式子的模样。依旧是洛谷的一道题,洛谷P1516, 点我传送看题.
题解:说的是两个青蛙在一个给定长度L圆圈上,这个圆圈是一个闭合的数轴,如下图是一个长度为4的圆圈。然后呢,青蛙初始分别站在两个给定的点x, y上,两个青蛙都向正方向跳,跳的步长不同,分别给定为m, n,但是,跳一次所用的时间相同。然后两只青蛙同时开始跳,问跳几次之后,两只青蛙会跳到一个点上,如果永远也跳不到,则输出 "Impossible".


不知不觉,把题目讲了一遍...
同样,这个过程可以转换成数学公式:(其中k$$\in$$N)
(x + km) % L = (y + kn) % L
根据 同余定理 的性质自行百度,
上式有:
x + km $$\equiv$$ y + kn (mod L)
有:
x - y $$\equiv$$ k(n - m) (mod L)
有:
k(n - m) = tL + x - y, 其中t$$\in$$Z.
有:
(n - m)k + L(-t) = x - y
可以看到变量就只有k, t,而我们要求的就是k的最小正整数解。
这个时候令n - m = a, t = b, x - y = c.该式变为ak + bt = c,但是还不能这样搞,因为要求a, b为正。而 n - m 不知道是不是为正,所以面对这个问题我们要判断一下,然后调一下式子左右的正负。具体实现看代码。我们化成的ak + bt = c和扩展欧几里得那个式子还是有点不一样。它式子右边不是gcd(a, b),不过这不是问题。我还是那句话,要想有整数解那就必须是ax + by = gcd(a, b)这种形式,否则就无整数解。但是你再仔细看看:
ax + by = gcd(a, b)
两边乘以$$\frac{c}{gcd(a, b)}$$得:
a($$\frac{cx}{gcd(a, b)}$$) + b($$\frac{cy}{gcd(a, b)}$$) = c
然后再令:
x = $$\frac{cx}{gcd(a, b)}$$
y = $$\frac{cy}{gcd(a, b)}$$
发现其实是一样的,所以对于ax + by = c 这种式子只要 c % gcd(a, b) = 0,就有整数解了。
接下来就没什么事了,套板子...
下面是AC代码:

//洛谷P1516 青蛙的约会
#include <stdio.h>
typedef long long ll;
ll exGcd(ll a, ll b, ll *x, ll *y)
{
    if(b == 0){
        *x = 1;
        *y = 0;
        return a;
    }
    ll res = exGcd(b, a % b, x, y);
    ll temp = *x;
    *x = *y;
    *y = temp - a / b * (*y);
    return res;
}
ll myabs(ll v)
{
    return v < 0 ? -1 * v: v;
}
int main(void)
{
    ll x, y, m, n, L, i, j, k, g;
    scanf("%lld%lld%lld%lld%lld", &x, &y, &m, &n, &L);
    k = n - m > 0? x - y: y - x;    //要保证ax+by = c中的a 和 b为正
    g = exGcd(myabs(n - m), L, &i, &j); //这里得 i 还不是结果,i * k / g 才是特解
    if(k % g != 0){ //不等于0是无解的情况
        printf("Impossible\n");
    }else{
        i = ((k / g * i) % (L / g) + (L / g)) % (L / g);    //特解转最小正整数解才是答案
        printf("%lld\n", i);
    }
    return 0;
}

好了,扩展欧几里得算法就这么多了,各位一起加油!!!

声明:Trikker的小破站|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 扩展欧几里得算法


分享一些学习成果