题解 | #最大公约数#
最大公约数
http://www.nowcoder.com/practice/cf4091ca75ca47958182dae85369c82c
求最大公约数
1、辗转相除法
gcd(a,b)=gcd(b,a%b)
若要求（a,b)的公约数等于（a,a%b）的公约数，当a%b==0时，b为最大公约数；
class Solution {
public:
int gcd(int a, int b) {
if(a%b==0){return b;}
else{return gcd(b,a%b);}
}
};2、更相减损法
性质：两个数的最大公约数等于两个数中较小的和两数之差的最大公约数。
class Solution {
public:
int gcd(int a, int b) {
int temp = abs(a - b); //取差的绝对值
while(temp != 0) //不断减去差的绝对值直到为0
{
a = b;
b = temp;
temp = abs(a - b);
}
return b;
}
};