gcd得最大公约数，辗转相除法理解
欧几里得算法_百度百科 (baidu.com)
——————
百度百科证法一的一些便于理解的细节：
我们求 a 和 b 的最大公约数。
（如果a是b的倍数，那么b就是最大公约数。）
a>b，a可以表示为 a = kb + r
设d为a和b的最大公约数
对上式等号左右两端同时除以d，得 a/d = kb/d + r/d
a/d 和 kb/d都是整数，那么r/d也是整数。那么r也是d的倍数。同时r<b，r与b的最大公约数也是d
( r<d是因为r = a%b （由a的表示可知))
那么问题就转化成求 b 与 r 的最大公约数。
即 gcd(a,b) = gcd(b,a mod b)
r会一直变小，为0时，b就是最大公约数了 （b最小为1，当b为1时，余数必然为0）
——————
（当然再进一次循环就是 a 与 0 。返回a即可）：
long long gcd(long long a,long long b)
{if (a<b)swap(a,b); if (b==0) return a;elsereturn gcd(a%b,b);
}