欧几里得算法
① 欧几里得算法（辗转相除法）
就是把上一轮有余数的除法计算中， 除数变为下一轮计算的被除数， 余数变为下一轮计算的除数， 一直这样计算下去， 直到最后一次计算余数为零， 在最后一轮计算中的被除数，即为所求的最大公约数。
举例： 105和85的最大公约数
第一轮计算 105÷85=1...20
第二轮计算 85÷20=4...5
第三轮计算 20÷5=4
第三轮没有余数， 因此 105和85的最大公约数就是第三轮计算的被除数 5.
至于C语言编程，下边是我自己写的G函数(思想就是辗转相除法求最大公约数)
int G(int x,int y)
{ int t;
while(y!=0)
{ t=x%y ;
x=y;
y=t;
}
return x;
}
② 扩展欧几里得算法 好懂一点
欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理：
定理：gcd(a,b) = gcd(b,a
mod b)
证明：a可以表示成a = kb +
r，则r = a mod b
假设d是a,b的一个公约数，则有
d|a,
d|b，而r = a - kb，因此d|r
因此d是(b,a
mod b)的公约数
假设d 是(b,a
mod b)的公约数，则
d | b , d
|r ，但是a = kb +r
因此d也是(a,b)的公约数
因此(a,b)和(b,a mod
b)的公约数是一样的，其最大公约数也必然相等，得证
欧几里德算法就是根据这个原理来做的，其算法用C++语言描述为：
int
Gcd(int a, int b)
{
if(b ==
0)
return a;
return
Gcd(b, a % b);
}
当然你也可以写成迭代形式：
int
Gcd(int a, int b)
{
while(b !=
0)
{
int r = b;
b = a % b;
a =
r;
}
return
a;
}
本质上都是用的上面那个原理。
补充:
扩展欧几里德算法是用来在已知a,
b求解一组x，y使得a*x+b*y=Gcd(a,b)(解一定存在，根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。下面是一个使
用C++的实现：
int
exGcd(int a, int b, int &x, int
&y)
{
if(b ==
0)
{
x = 1;
y = 0;
return a;
}
int r =
exGcd(b, a % b, x, y);
int t =
x;
x =
y;
y = t - a
/ b * y;
return
r;
}
把这个实现和Gcd的递归实现相比，发现多了下面的x,y赋值过程，这就是扩展欧几里德算法的精髓。
可以这样思考:
对于a' = b,
b' = a % b 而言，我们求得 x, y使得 a'x + b'y = Gcd(a', b')
由于b' = a
% b = a - a / b * b (注：这里的/是程序设计语言中的除法)
那么可以得到:
a'x + b'y
= Gcd(a', b') ===>
bx + (a - a / b * b)y = Gcd(a', b') = Gcd(a, b)
===>
ay +b(x - a / b*y) = Gcd(a, b)
因此对于a和b而言，他们的相对应的p，q分别是
y和(x-a/b*y).
在网上看了很多关于不定方程方程求解的问题，可都没有说全，都只说了一部分，看了好多之后才真正弄清楚不定方程的求解全过程，步骤如下：
求a * x
+ b * y = n的整数解。
1、先计算Gcd(a,b)，若n不能被Gcd(a,b)整除，则方程无整数解；否则，在方程两边同时除以Gcd(a,b)，得到新的不定方程a'
* x + b' * y = n'，此时Gcd(a',b')=1;
2、利用上面所说的欧几里德算法求出方程a' * x + b' * y = 1的一组整数解x0,y0，则n' * x0,n' *
y0是方程a' * x + b' * y = n'的一组整数解；
3、根据数论中的相关定理，可得方程a'
* x + b' * y = n'的所有整数解为：
x = n' * x0 + b' * t
y = n' * y0 - a' * t
(t为整数)
上面的解也就是a * x + b * y = n 的全部整数解。
步骤如下：
扩展欧几里德算法－求解不定方程，线性同余方程：
解不定方程ax + by = n的步骤如下:
(1)计算gcd(a, b). 若gcd(a, b)不能整除n，则方程无整数解；否则，在方程的两边同除以gcd(a, b)，
得到新的不定方程a'x + b'y = n'，此时gcd(a', b') = 1
(2)求出不定方程a'x + b'y = 1的一组整数解x0, y0，则n'x0，n'y0是方程a'x + b'y = n'的一组整数解。
(3)根据&@^%W#&定理，可得方程a'x + b'y = n'的所有整数解为：
x = n'x0 + b't
y = n'y0 - a't
(t为整数)
这也就是方程ax + by = n的所有整数解
利用扩展的欧几里德算法，计算gcd(a, b)和满足d = gcd(a, b) = ax0 + by0的x0和y0，
也就是求出了满足a'x0 + b'y0 = 1的一组整数解。因此可得：
x = n/d * x0 + b/d * t
y = n/d * y0 - a/d * t
(t是整数)
program oujilide;
var i,j,a,b,c,d,x,y:longint;
function gcd(a,b:longint):longint;
var i:longint;
begin
if a=0 then exit(b);
if b=0 then exit(a);
gcd:=gcd(b,a mod b);
end;
procere extend_gcd(a,b:longint;var x,y:longint);
var i,j:longint;
begin
if b=0 then
begin
x:=1;
y:=0;
exit
end;
extend_gcd(b,a mod b,x,y);
i:=x;
x:=y;
y:=i-(a div b)*x;
end;
begin
assign(input,'oujilide.in');
reset(input);
assign(output,'oujilide.out');
rewrite(output);
read(a,b,c);
d:=gcd(a,b);
if c mod d=0 then begin a:=a div d; b:=b div d; c:=c div d; end
else begin writeln('No answer!'); exit; end;
extend_gcd(a,b,x,y);
x:=c*x;
y:=c*y;
writeln(x,' ',y);
end.
③ 欧几里得算法
计算过程一模一样，只是最后对1001取模：
1 = 167 - 166
= 167 - (834 - 4 * 167)
= 5 * 167 - 834
= 5 *(1001 - 834) - 834
= 5 * 1001 - 6 *834
= 5 * 1001 - 6 * (3837 -3 *1001)
= 23 * 1001 - 6 *3837
然后对等式两端同时除以模1001得
6 * 3837 = 1 (mod 1001)
于是 x ＝ 6
④ 扩展欧几里得算法
//欧几米德算法 //算法描述：给定两个正整数m和n,求他们的最大公因子。 //1.[求余数]用m除以n并令r为所得余数 //2.[余数为0]若r=0,则算法结束，n即为所求答案 //3.[互换]置m←n,n←r,并返回步骤1。 #include <cstdlib> #include <iostream> using namespace std; int main(int argc, char *argv[]) { int n,m; int r; cout << "输入两个数（M，N）："; cin >> m >> n; cout << m << "和" << n << "的最大公约数为"; while(r!=0) { r=m %n; m=n; n=r; } cout << m<< endl; system("PAUSE"); return EXIT_SUCCESS; }
麻烦采纳，谢谢!
⑤ 用java实现欧几里得算法🌝
publicstaticvoidmain(String[]args){
Scannerscanner=newScanner(System.in);
inta,b;
a=scanner.nextInt();
b=scanner.nextInt();
System.out.printf("%d和%d的最大公约数为：%d",a,b,Gcd(a,b));
}
privatestaticintGcd(intM,intN){
intRem;
while(N>0){
Rem=M%N;
M=N;
N=Rem;
}
returnM;
}
⑥ 关于欧几里得算法，主要是看不懂。请高手指点迷津。。。。
1、 欧几里德算法：给定两个正整数m和n，求他们的最大公因子，即能够同时整除m和n的最大的正整数。
E1：【求余数】以n除m并令r为所得余数（我们将有0<=r<n）。
E2：【余数为0？】若r=0，算法结束；n即为答案。
E3：【互换】置mßn,nßr,并返回步骤E1.
证明：
我们将两个正整数m和n的最大公因子表示为：t = gcd（m，n）；
重复应用等式：gcd（m，n）= gcd（n，m mod n）直到m mod n 等于0；
m可以表示成m = kn + r；则 r = m mod n ， 假设 d是 m 和 n的一个公约数，则有：
d|m 和 d|m 而 r =m – kn ，因此 d|r ，因此 d 是 (n,m mod n) 的公约数；假设 d 是 (n,m mod n) 的公约数，
则 d|n ，d|r ，但是 m=kn+r ，因此 d 也是 (a,b) 的公约数；因此 (a,b) 和
(b,a mod b) 的公约数是一样的，其最大公约数也必然相等，得证。
具体步骤描述如下：
第一步：如果 n=0 ，返回 m 的值作为结果，同时过程结束；否则，进入第二步。
第二步：用 n 去除 m ，将余数赋给 r 。
第三步：将 n 的值赋给 m，将 r的值赋给 n，返回第一步。
伪代码描述如下：
Euclid(m,n)
// 使用欧几里得算法计算gcd(m,n)
// 输入：两个不全为0的非负整数m，n
// 输出：m，n的最大公约数
while n≠0 do
r ← m mod n
m ← n
n ← r
注：(a,b) 是 a,b的最大公因数
(a,b)|c 是指 a,b的最大公因数 可以被c整除。
java实现：
package algorithm;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class GreatestCommonDivisor {
int a,b,temp = 0;
public static void main(String args[]) throws IOException {
GreatestCommonDivisor gcd = new GreatestCommonDivisor();
gcd.readNum();
gcd.MaxNum();
System.out.print(gcd.a+"和"+gcd.b+"的最大公约数是:");
while (gcd.b != 0) {
gcd.temp = gcd.b;
gcd.b = gcd.a % gcd.b;
gcd.a = gcd.temp;
}
System.out.println(gcd.temp);
}
//输入两个正整数,中间用空格分开.
public void readNum() throws IOException{
BufferedReader buf = new BufferedReader(new InputStreamReader(System.in));
String str = buf.readLine();
for(int i = 0;i<str.length();i++){
if(str.charAt(i)==' ' && temp == 0){
a = Integer.parseInt(str.substring(temp,i));
temp = i;
b = Integer.parseInt(str.substring(temp+1,str.length()));
break;
}
}
}
public void MaxNum(){
if (a < b) {
temp = b;
b = a;
a = temp;
}
}
}
⑦ 用欧几里得算法找x和y!!
就是8=144*1-1(1000-144*6)
=144*1-1000+144*6（分配律）
=144*（6+1）-1000（结合律）
⑧ 什么是欧几里得算法，它有什么意义
欧几里得算法即辗转相除法，用以求两个数的最大公约数（或者最小公倍数）
证明如下
假设x,y的最大公约数为d
且设x=k1*d，y=k2*d;
则有z=x-y=(k1-k2)*d;
也必定能被d整除，所以通过两个数不断辗转，直到其中一个变为0为止，以此最终快速得出两个数的最大公约数。
在算法的应用上是用求余以加速运算的速度。
总的来说，欧几里得算法的意义就是快速求得两个数的最大公约数。
⑨ 欧几里得算法是什么
欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
辗转相除法的算法步骤为，两个数中用较大数除以较小数，再用出现的余数除除数。
再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。
辗转相除法是利用以下性质来确定两个正整数a和b的最大公因子的：
1、若r是a ÷ b的余数，且r不为0，则gcd(a,b) = gcd(b,r)。
⒉、a和其倍数之最大公因子为a。
另一种写法是：
⒈、令r为a/b所得余数（0≤r），若r= 0，算法结束；b即为答案。
⒉、互换：置a←b，b←r，并返回第一步。
⑩ 欧几里得算法求过程
就是把上一轮有余数的除法计算中， 除数变为下一轮计算的被除数， 余数变为下一轮计算的除数， 一直这样计算下去， 直到最后一次计算余数为零， 在最后一轮计算中的被除数，即为所求的最大公约数。