### GCD GCD，即最大公约数，指两个或多个整数共有约数中最大的一个。 求最大公约数有多种方法，常见的有质因数分解法、短除法、辗转相除法、更相减损法。 在一般竞赛中，求GCD一般使用辗转相除法。其复杂度约为O(log(max(n,m)))，是一种很高效的算法。而且其代码量也非常少 ~~~ int gcd(int a,int b) { return b ? gcd(b,a%b) : a; } ~~~ #### 拓展性质 如果GCD( n , a ) = 1 , n>a 则GCD( n , n - a ) = 1。 可以用反证法证明 > 假设GCD( n , n - a ) = i ( i > 1 )，设 n = k1 \* i，n - a = k2 \* i（ k1 > k2 > 0 ）， > > 则 n -( n -a ) = a = (k1-k2) \* i，与GCD( n , a ) = 1 矛盾，所以上述性质成立。