（扩展）欧几里德算法

叁歲伎倆 2022-08-02 02:20 141阅读 0赞

欧几里德是用来求最大公约数的，可以把它看成是状态转移，

对任意两个数a，b（a>b），d=gcd（a，b），如果b不为零，那么gcd（a，b）=gcd（b，a%b）

证明： 令 r=a%b，即存在k，使得 a=b\*k+r，那么r=a-b\*k；显然r>=0,  r%d=（（a%d）-（b\*k）%d）%d，因为a%d=b%d=0，所以r%d=0；

因此求gcd（a，b）可以转移到求gcd（b，a%b），那么这就是个递归过程了，那什么时候递归结束呢，想一下，a，b不能为零，则可以把当b为零，作为递归的结束（当然还可以以其它结束条件），这就是求最大公约数的方法可以以其它结束条件），这就是求最大公约数的方法

int gcd(int a,int b)
    {
        if(b==0)return a;
     
        else return gcd(b,a%b);
     }

是不是很简单呀.

理解了上面，那么扩展欧几里得就能很容易理解了，对任意a，b（a>b），我们列出这样一个式子： a\*x+b\*y=gcd(a,b);

不要觉得扩展欧几里得很牛逼，它就是一个算x，y的一个方法，只是在上面gcd中多了处理x，y的步骤

我们这样来想：

已知当前的一个状态：a1  b1  x1  y1,    a1\*x1+b1\*y1=gcd(a1,b1),注意这里的a1，b1是求gcd（a，b）中的一个状态，

假设 （a1，b1）是由（a0，b0）转移过去的

那么：   a1=b0 ;     b1=a0%b0=a0-k\*b0 （k=int(a0/b0)）;gcd(a0,b0)=gcd(a1,b1);

代入a1\*x1+b1\*y1=gcd(a1,b1),变化成：b0\*x1+(a0-k\*b0)\*y1=gcd(a1,b1)=gcd(a0,b0);

a0\*y1+b0\*(x1-k\*y1)=gcd(a0,b0);

这样可以得到： x0=y1;  y0=x1-k\*y1;(理解这个过程了么，由当前状态可以算出上一状态的x，y，即当前状态可以由它的下一个状态的x，y得到)

int exGcd(int a,int b,int &x,int &y)
    {
    	if(b==0)
    	{
    		x=1;
    		y=0;
    		return a;// 此时a是最开始（a,b）的最大公约数，那么  gcd（a,b）*1+ 0*0=gcd(a,b),肯定对的，在这里，我认为，y可以为任何值都对
    	}
    	
    	int d=exGcd(b,a%b,y,x);
    	y-=a/b*x;
    	return d;//返回最大公约数
    }

**需要注意一点的就是方程得到的解不止一个是一个通解！**

**关于求解二元一次不定方程ax+by=c**

首先，如果c不是gcd(a,b)的倍数，方程显然无解。

扩展欧几里得求解的是ax+by=gcd(a,b)=1的可行解，但是题目中并没有说c与a,b互质之类的条件，所以需要在开始时两边同时除以gcd(a,b)。

设d=gcd(a,b)

设a'=a/d,b'=b/d,c'=c/d,

则下面需要求解a'x+b'y=c'的整数解，而gcd(a',b')=1，

则我们只需求a'x+b'y=1的可行解

直接使用扩展欧几里得，得到(x',y'),则最终解为x'\*c',y'\*c'设为(x0,y0)。

现在得到了一组可行解，但是如何得到通解呢？

将(x0,y0)代入ax+by=c，则有

a\*(x0)+b\*(y0)=c

通过拆添项，可有：

a\*(x0+1\*b)+b\*(y0-1\*a)=c

a\*(x0+2\*b)+b\*(y0-2\*a)=c

a\*(x0+3\*b)+b\*(y0-3\*a)=c

……

a\*(x0+k\*b)+b\*(y0-k\*a)=c  (k∈Z)

至此，我们得到了通解的方程

**x=x0+k\*b**

**y=y0-k\*a  (k∈Z)**

这样，所有满足ax+by=c的可行解都可求出。

发表评论取消回复

表情：

评论列表（有 0 条评论，141人围观）

还没有评论，来说两句吧...

相关阅读

相关欧几里得和扩展欧几里得算法

（一）欧几里得算法又称辗转相除法，是求解两个数的最大公约数的算法，基本定义为：设 a=qb+r，其中a，b，q，r都是整数，则：gcd（a，b）= gcd（b，r）利用

ゞ浴缸里的玫瑰/ 2022年08月21日 03:20/ 0 赞/ 252 阅读

相关 POJ 2115-C Looooops-扩展欧几里德算法

C Looooops <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

╰半橙微兮°/ 2022年08月21日 01:12/ 0 赞/ 165 阅读

相关 GCD ExGCD 扩展欧几里德算法证明与算法

\include <iostream> using namespace std; //扩展欧几里德算法 int ExGCD(int a, int b, int& x, int&

た入场券/ 2022年08月04日 13:50/ 0 赞/ 138 阅读

相关（扩展）欧几里德算法

欧几里德是用来求最大公约数的，可以把它看成是状态转移，对任意两个数a，b（a>b），d=gcd（a，b），如果b不为零，那么gcd（a，b）=gcd（b，a%b）

叁歲伎倆/ 2022年08月02日 02:20/ 0 赞/ 142 阅读

相关扩展欧几里得算法

问题描述：求解二元一次方程ax+by=c。问题分析：上述的二元一次方程可以用同余方程来进行描述：ax≡cmod(b) 两个问题可以进行转换，但是都可以用扩展的欧几

心已赠人/ 2022年06月15日 10:00/ 0 赞/ 248 阅读

相关详解--欧几里德算法

扩展欧几里德算法谁是欧几里德？自己百度去先介绍什么叫做欧几里德算法有两个数 a b，现在，我们要求 a b 的最大公约数，怎么求？枚

逃离我推掉我的手/ 2022年06月11日 07:47/ 0 赞/ 203 阅读

相关欧几里德算法

原文转载：博主——AdemJensen[https://blog.csdn.net/rentenglong2012/article/details/68944518][http

淩亂°似流年/ 2022年05月08日 07:00/ 0 赞/ 227 阅读

相关欧几里德与扩展欧几里德算法

先参考一篇比较优秀的文章：[欧几里德算法][Link 1] 欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。基本算法：设a=qb+r，

淡淡的烟草味﹌/ 2022年05月05日 14:28/ 0 赞/ 183 阅读

相关扩展的欧几里德算法

扩展欧几里得算法对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

刺骨的言语ヽ痛彻心扉/ 2022年04月22日 11:18/ 0 赞/ 181 阅读

相关扩展欧几里得算法

下面直接使用简称exgcd就好。先引入紫书上的一个经典问题，求直线方程ax+by+c=0的所有整数解。我们先来看一个简单的，求ax+by=gcd(a,b)的一组整数解。

今天药忘吃喽~/ 2021年09月29日 21:02/ 0 赞/ 410 阅读