【问题描述】输入任意两个自然数，求它们的最大公约数。
【样例输入】
8 40
【样例输出】
8
问题解析：
今天我们讲一个数学技巧，欧几里德算法。
（1）欧几里德算法也叫辗转相除法，是指用于计算两个正整数a，b的最大公约数。
（2）算法原理：
对于任意两个正整数a和b，如果a/b = q…r（a除以b的商是q，余数是r），那么a和b的最大公约数等于b和r的最大公约数。
具体的算法过程如下：
（1）a/b = q1…r1。
（2）如果r1=0，则a和b的最大公约数为b。
如果r1≠0，则继续除法运算：b/r1=q2…r2。
（3）如果r2=0，则a和b的最大公约数为r1。
如果r2≠0，则继续除法运算：r1/r2=q3…r3。
（4）重复执行上述过程，直到能够整除为止。余数为0时的除数就是a和b的最大公约数。
所以根据欧几里德算法，求解a和b的最大公约数也就是重复执行除法运算并判断余数是否为0的过程。
首先我们使用while循环来模拟上述过程：
【参考程序】
#include <iostream>
using namespace std;
int main(){
int a1,b1,a,b,r;
cin >> a1 >> b1;
a = max(a1,b1);
b = min(a1,b1);
r = a%b;
while(r!=0) {
a = b;
b = r;
r = a%b;
}
cout << b << endl;
return 0;
}
上面的算法过程其实也是一个递归的过程，递归关系式为：gcd(a,b)=gcd(b,r)。
接下来我们使用递归算法来模拟上述过程：
【参考程序】
#include <iostream>
using namespace std;
int gcd(int a,int b){
int r = a % b;
if(r == 0){
return b;
}else{
return gcd(b,r);
}
}
int main(){
int a1,b1,a,b;
cin >> a1 >> b1;
a = max(a1,b1);
b = min(a1,b1);
cout << gcd(a,b) << endl;
return 0;
}
转自公众号：
noip案例讲解