zuidagongyueshu.cpp

来自「简单求最大公约数小程序,实现两数的公约数输出,仅供参考」· C++ 代码 · 共 70 行

#include <stdio.h>
#include <iostream.h>
#include <fstream.h>
#include <assert.h>
#include <math.h>
#include <stdlib.h>
int gcd(int a,int b,int &ar,int &br)
 {
  int x1,x2,x3;
  int y1,y2,y3;
  int t1,t2,t3;
  if(a==0)
  {
    //有一个数为0，就不存在乘法逆元
    ar=0;
    br=0;
    return b;
  }
  if(b==0)
  {
    ar=0;
    br=0;
    return a;
  }
  x1=1;
  x2=0;
  x3=a;
  y1=0;
  y2=1;
  y3=b;
  int k;
  for(t3=x3%y3;t3!=0;t3=x3%y3)
  {
   k=x3/y3;
   t2=x2-k*y2;
   t1=x1-k*y1;
   x1=y1;
   x1=y2;
   x3=y3;
   y1=t1;
   y2=t2;
   y3=t3;
  }
  if(y3==1)
  {
   //有乘法逆元
   ar=y2;
   br=x1;
   return 1;
  }
  else
  {
   //公约数不为1，无乘法逆元
   ar=0;
   br=0;
   return y3;
  }
 }

int main() 
{ 
int a,b,i,x,y; 
while(1) 
{ 
scanf("%d%d", &a, &b); 
if (a==0 && b==0) 
break; 
printf("最大公约数为%d\n",gcd(b,a,x,y)); 
} 
}