浅谈扩展欧几里得[exgcd] By cellur925

关于扩展欧几里得从寒假时就很迷，抄题解过了同余方程，但是原理并不理解。

今天终于把坑填上了qwq。

由于本人太菜，不会用markdown，所以这篇总结是手写的（什么）。（字丑不要嫌弃嘛）

********Update9.28**********

刚刚我们求出的是一组特值，那么如何求通值?

约定：设x0,y0为一组特解，t为任意整数，设a>b（不行再交换）

那么有　　x=x0+b/gcd*t
　　　　　y=y0-a/gcd*t

*******************************

奉上三道例题：

Ep1 青蛙的约会 Luogu P1516

花姐姐（@皎月半洒花）说的太棒了，我都不忍再去添加什么。

奉上链接，侵删！

Code

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 ll xx,yy,ans;

 ll x,y,m,n,t;

 ll exgcd(ll a,ll b,ll &xx,ll &yy)

 {

     if(!b)

     {

         xx=;

         yy=;

         return a;

     }

     ans=exgcd(b,a%b,xx,yy);

     ll tmp=xx;

     xx=yy;

     yy=tmp-a/b*yy;

     return ans;

 }

 int main()

 {

     scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&t);

     ll a=n-m,z=x-y;

     if(a<) a=-a,z=-z;

     exgcd(a,t,xx,yy);

     if(z%ans) printf("Impossible");

     else printf("%lld",((xx*(z/ans))%(t/ans)+(t/ans))%(t/ans));

     return ;

 }

注意体会同余方程转线性方程的思想与做法！

Ep2 倒酒 Luogu P1292

容易看出，得到酒的最小体积是gcd(a,b),这种思想在我以前写的“瓶子和燃料”一题中有所体现。模拟一下就可以发现，之后的次数就是ax+by=gcd(a,b)的一组最小解。

套exgcd板子就行了，但是注意取最小值的那一部分，其实感觉每个题取最小值的方法都各有千秋，都要独立思考，这是关键。

一个不错的题解，侵删。

Code

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 typedef long long ll ;

 ll a,b,x,y,ans;

 ll exgcd(ll a,ll b,ll &x,ll &y)

 {

     if(!b)

     {

         x=;y=;

         return a;

     }

     ll d=exgcd(b,a%b,x,y);

     ll tmp=x;

     x=y;

     y=tmp-y*(a/b);

     return d;

 }

 int main()

 {

     scanf("%lld%lld",&a,&b);

     ans=exgcd(a,b,x,y);

     printf("%lld\n",ans);

     a/=ans,b/=ans;

     while(x>) x-=b,y+=a;

     while(x+b<=&&y>=a) x+=b,y-=a;

     printf("%lld %lld",-x,y);

     return ;

 }

ps:while(x>0)那里如果写成while(x)竟会死循环，还是老实一点吧。

Ep3 同余方程 Luogu P1082

把同余方程转一下。直接套exgcd模板，取最小值部分，lyd老师的讲解：

“用exgcd求出一组特解x0,y0,则x0就是原方程的一个解，通解为所有膜b与x0同余的整数，通过取模操作把解的范围移动到1~b”之间，就得到了最小正整数解。”

Code

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 int exgcd(int a,int b,int &x,int &y)

 {

     if(b==)

     {

           x=;

           y=;

           return a;

     }

     int r=exgcd(b,a%b,x,y);

     int t=x;

     x=y;

     y=t-a/b*y;

     return r;  

 }

 int main()

 {

     int a,b,x,y;

     scanf("%d%d",&a,&b);

     exgcd(a,b,x,y);

     cout<<(x+b)%b;

     return ;

 }

巴特西

浅谈扩展欧几里得[exgcd] By cellur925

最新文章

热门文章