最大公约数（Greatest Common Divisor，即gcd）是指balabala。。。请自行百度。。。。。
如何用编程来实现呢？我最初的想法是这样的：
[cc lang = “cpp” escaped = “true”]
//从两个数中较小的开始，向下遍历，第一个满足条件的即为最大公约数
int gcd(int a, int b) {
int temp;
if (a > b) {
temp = a;
a = b;
b = temp;
}
for (int i = a; i > 0; i–) {
if (a % i == 0 && b % i == 0) return i;
}
return 1;
}
[/cc]
但这种算法的时间复杂度是线性的，相对较高，无法通过某些OJ系统。
所以我们有了以下这种算法，它依据的原理是“辗转相除法”（我第一次get这个算法并看到名称时，突然想到小学还是初中似乎是学过的。。。然而居然忘记了，罪过罪过。。。。。
[cc lang = “cpp” escaped = “true”]
//辗转相除法法法法法法法法法法法法法法法法法法法法法法法法法法法法
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
[/cc]
唔，怎么样。。。。
虽然没细算，但目测时间复杂度怎么也是根号n以下咯。。。。。
啊，我爱数学。。。。～～～
