Euclid除法

Euclid除法过程.png

例题1:

设a=46480,b=39423,计算(a,b)
利用广义欧几里得除法.

1. 方法一:最小非负整数
   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];
}