Exgcd(拓展欧几里得算法)的初步理解-Toy模板网

这篇具有很好参考价值的文章主要介绍了Exgcd(拓展欧几里得算法)的初步理解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

裴蜀定理

若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

Exgcd

针对于一次不定方程ax+by=c进行求解,利用以上的裴蜀定理可以进行求解,当然要满足 gcd(a,b)|c 这个前置情况这个时候实际上就是对于

b*x+(a%b)*y=d(辗转相除法求得)

a%b=a-(a/b)*b

进行带入即可得到:

a*y-b*(x-(a/b)*y)=d

和原式ax+by=d对比可以知道辗转相除的过程中:

x=y,y=x-(a/b)*y

所以我们可以得到exgcd的过程为:

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

解决了exgcd的过程,我们就要看它的作用,解一次不定方程ax+by=c.此时求出来的x,y还不是该方程的解,此时还是ax+by=gcd(a,b)的解(不满足gcd(a,b)|c则无解).我们将x和y均除以gcd(a,b)在乘以一个c就是一组方程的特解.那么如何求通解呢?

取一组x,y和刚刚求出来的特解x0,y0:

ax+by=ax0+by0

a(x-x0)=b(y0-y)两边同时除以d(即为gcd(a,b))

a/d*(x-x0)=b/d*(y0-y)

已知此时a/d和b/d是互质的,那么可知(x-x0)和b/d,(y0-y)和a/d成倍数关系,可以进一步退出下面的式子:

x=x0+k*b/d;

y=y0-k*a/d;

注意此时的k可以取任意值,那么这里的加号和减号表示的就是两者符号相反,而不是真正意义上的家或者减.这就是通解.

利用这个我们也可以求出x,y的最小值,就直接用(x%(b/d)+(b/d))%(b/d)即可,y的最小值同理.当x取最小值时,y取最大,反之亦然.

下面是实站例子:

【模板】二元一次不定方程 (exgcd) - 洛谷https://www.luogu.com.cn/problem/P5656板子题.上代码,代码有注释:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
    if(b==0)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b*x);
    return d;
}
//exgcd板子
void solve()
{
    int a,b,c,x,y;
    scanf("%lld%lld%lld",&a,&b,&c);
    int d=exgcd(a,b,x,y);
    if(c%d)
    {
        printf("-1\n");
        return ;
    }
//这表示不符合裴蜀定理,不成立
    else
    {
        x=x*c/d;
        y=y*c/d;
        int minx=(x%(b/d)+b/d)%(b/d);
        if(minx==0)
            minx+=b/d;
        int miny=(y%(a/d)+a/d)%(a/d);
        if(miny==0)
            miny+=a/d;
//分别求出x,y的最小值
        int maxx=(c-b*miny)/a;
        int maxy=(c-a*minx)/b;
        if(maxx<=0||maxy<=0)
        {
            printf("%lld %lld\n",minx,miny);    
            return ;
        }
//求出x,y的最大值,原理就是当x,y分别取最小时,对方都是处于最大值的状态
//当最大值不是正整数时,只输出最小的情况
        int num=(maxx-minx)/(b/d)+1;
        printf("%lld %lld %lld %lld %lld\n",num,minx,miny,maxx,maxy);
    }
    return;
}
signed main()
{
    int t;
    scanf("%d",&t);
    while(t--)
        solve();
    return 0;
}

青蛙的约会 - 洛谷https://www.luogu.com.cn/problem/P1516这题老演员了,见挺多次了.

这题和上题稍微不太一样,我们不能直接用exgcd,要列出式子然后自己进行变形,变为exgcd的形式然后进行求解.我们设跳跃了p次,青蛙A调了q圈才追上青蛙B,所以我们可以列出式子:

(m-n)q=pl+(y-x)

进行变形后:

(m-n)q-pl=(y-x)

形似ax+by=c,直接带入exgcd进行计算即可,注意用裴蜀定理判断是否能成功追上.

代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=(a/b*x);
    return d;
}
void solve()
{
    int x,y,m,n,l,p,q;
    scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
    int d=exgcd(m-n,l,p,q);
    if((y-x)%d)
    {
        printf("Impossible\n");
    }
    else
    {
        l=abs(l/d);
        p=p*(y-x)/d;
        printf("%lld\n",(p%l+l)%l);
    }
    return ;
}
signed main()
{
    solve();
    return 0;
}

当然有一些同余方程也可以进行变形:

可以变形为ax+km=b文章来源地址https://www.toymoban.com/news/detail-602290.html

到了这里，关于Exgcd(拓展欧几里得算法)的初步理解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！