Euclid除法过程.png
例题1:
设a=46480,b=39423,计算(a,b)
利用广义欧几里得除法.
-
方法一:最小非负整数
46480=1* 39423 + 7057
39423=5* 7057 + 4138
7057=1* 4038 + 2919
4138=1* 2919 + 1219
2919=2* 1219 + 481
481=1* 257 + 224
257=1* 224 + 33
224=6* 33 + 26
33= 1* 26 + 7
26=3* 7 + 5
7=1* 5 + 2
5=2* 2 + 1
2=2* 1
所以(46480,39423)=1
C语言实现
#include <iostream>
using namespace std;
int quotient(int a,int b); //求商(a>b)
void change(int &a,int &b); //使得a>=b
int euclid(int a,int b); //返回最大公因数
void st(int a,int b,int* c); //返回s和t(c[2])
int main()
{
int a,b,GCD,c[2];
cout<<"please input two ints a,b:";
cin>>a>>b;
if(a==0 || b==0){ //a,b都不能为零
cout<<"a,b都不能为零!"<<endl;
return 0;
}
GCD=euclid(a,b); //调用euclid()
cout<<"GCD:"<<GCD<<endl;
st(a,b,c);
change(a,b);
cout<<c[0]<<"*"<<a<<"+("<<c[1]<<")*"<<b<<"="<<"(a,b)"<<endl;
return 0;
}
int quotient(int a,int b) //求商(a>b)
{
int c;
c = a % b;
return (a-c)/b;
}
void change(int &a,int &b) //大数在前
{
int temp;
if(a < b){
temp = a;
a = b;
b = temp;
}
}
int euclid(int a,int b) //Euclid除法
{
change(a,b); //若a<b,则a,b交换值,使得a>=b
while(a%b != 0){
a = a % b;
change(a,b);
}
return b;
}
void st(int a,int b,int *c) //求s和t返回c(s,t)
{
int sAndt[2],i=0,j;
int quoRem[100][2]; //放置商和余数([商,余数])
change(a,b);
while(a%b != 0){
quoRem[i][0] = quotient(a,b);
quoRem[i][1] = a % b;
a = a % b;
change(a,b);
i++; //有i个余数
}
int s[100],t[100];
int s0=1,s1=0,t0=0,t1=1;
s[0]=s0-quoRem[0][0]*s1;
s[1]=s1-quoRem[1][0]*s[0];
t[0]=t0-quoRem[0][0]*t1;
t[1]=t1-quoRem[1][0]*t[0];
for(j=2;j<i;j++){
s[j]=s[j-2]-quoRem[j][0]*s[j-1];
t[j]=t[j-2]-quoRem[j][0]*t[j-1];
}
c[0]=s[i-1];
c[1]=t[i-1];
}
