欧几里得算法和扩展的欧几里得算法

欧几里得算法又称辗转相除法

给定两个正整数m,n。求他们的最大公约数，算法代码为

#include "stdafx.h"

#include<iostream>

using namespace std;

int gcd(int m,int n)

{

int r=n%m;

while(r!=0)

{

n=m;

m=r;

r=n%m;

}

return m;

}

int _tmain(int argc, _TCHAR* argv[])

{

int m,n;

cin>>m>>n;

if(m>n)

{

int temp=m;

m=n;

n=temp;

}

int h=gcd(m,n);

cout<<"最大公约数是"<<h<<endl;

cout<<"最小公倍数是:"<<(m*n)/gcd(m,n)<<endl;

return 0;

}

扩展的欧几里得算法是：

给定两个整数m、n,我们计算它们的最大公约数d和两个整数a和b，使得am+bn=d

算法代码如下

#include "stdafx.h"

#include<iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int m,n,a1,b,a,b1,c,d,q,r,t;

a1=b=1;

a=b1=0;

cin>>m>>n;

c=m;

d=n;

q=c/d;

r=c%d;

while(r!=0)

{

c=d;

d=r;

t=a1;

a1=a;

a=t-q*a;

t=b1;

b1=b;

b=t-q*b;

q=c/d;

r=c%d;

}

cout<<d<<endl;

cout<<a<<" "<<b<<endl;

return 0;

}