首页 > 技术文章 > 7. 最大公约数(辗转相除法)

csgc0131123 2016-03-18 06:07 原文

 


题目描述 Description

求两个数A和B的最大公约数。 1<=A,B<=2^31-1

输入描述 Input Description

两个整数A和B

输出描述 Output Description

最大公约数gcd(A,B)

样例输入 Sample Input

8 12

样例输出 Sample Output

4

自己的答案:

#include

using namespace std;

#include

long long a,b,yu;

int main()

{

       cin>>a>>b;

       if(a

       swap(a,b);

       yu=a-b;

       while(yu!=0)

       {

              a=b;

              b=yu;

              if(a

           swap(a,b);//不要忘记,始终让a大于b才行,

              yu=a-b;

       }

       if(yu==0)

       printf("%d",b);

       return 0;

}

推荐阅读