18.2.13 codevs1212 最大公约数

题目描述 Description

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

输入描述 Input Description

两个整数A和B

输出描述 Output Description

最大公约数gcd(A,B)

样例输入 Sample Input

8 12

样例输出 Sample Output

 1 #include <iostream>
 2 #include<math.h>
 3 
 4 using namespace std;
 5 
 6 long dig(long x,long y)//y>x
 7 {
 8     long yy=x,xx=y%x;
 9     if(xx==0)
10         return x;
11     else
12         dig(xx,yy);
13 }
14 
15 int main()
16 {
17     long x,y;
18     cin>>x>>y;
19     if(x<=y)
20         cout<<dig(x,y);
21     else
22         cout<<dig(y,x);
23     return 0;
24 }

View Code

求解最大公约数最常见的两种办法：辗转相除法和更相减损法

难道只有我一个人完全不知道这两种方法是啥玩意？！

辗转相除法

注定失败的战争，也要拼尽全力去打赢它；就算输，也要输得足够漂亮。