欧几里得算法核心： gcd( a ,b ) = gcd( b , a%b ) ，其中 gcd 表示 a 和 b 的最大公约数；

证明： 设 a 和 b 的最大公约数为 c ； 则有 c = gcd( a , b ) ; 设 a = x * c , b = y * c , 其中 x 与 y 互质 （因为 c 是最大公约数） 设 g = a%b = a - i * b = (x - i * y ) * c , 其中 i = [ a / b ] ,向下取整 ； 又 b = y * c ， 且易得 x - i * y 与 y 互质；（下面会证明） 则有 b 与 g 的最大公约数为 c , 又 g = a%b， 则 gcd( a, b ) = gcd( b , a%b );

接下来，证明 x - i * y 与 y 互质 , 反证法： 设 x - i * y 与 y 不互质； 则 x - i * y 与 y 存在最大公约数 k ( k>1 ) ; 设 x - i * y = n * k, y = m * k, 其中 n 和 m 互质； 把 y = m * k, 代入 x 中 得： x = (n + i * m ) * k 又 y = m * k , 故 x 与 y 不互质 ，与 上述证明矛盾（前面设x，y是互质的）； 所以 x - i * y 与 y 互质 ；

证毕； gcd( a , b ) = gcd( b , a%b )，求解 a、b 的最大公约数 ，化为 求解b 、a%b 的最大公约数；

符合递归 大问题化成小问题 求解的特性（也可以用循环求解） ;

当前递归到 a%b == 0时（b 整除 a）， 即 下一次递归的 b‘ = 0;

下一次递归 的 a’ ，即为当前层 的 b，为最大公约数；

int gcd(int a,int b)
{
    return b? gcd(b,a%b) : a;
}

复杂度分析 时间复杂度证明 证明之前先熟悉这些知识：

1. m mod n 的结果在 [0,n-1] 之间，如果 n > m /2 ，则 m mod n 的结果就是 m -n
2. m mod n< m/2

对2的证明： 记 rem 为 m mod n 如果 $n \leq \frac{m}{2}$,由1可知结论成立。 如果 $n> \frac{m}{2}$ ,则用1可知，$rem=m-n < m- \frac{m}{2} = \frac{m}{2}$ ,则结论成立。

原文链接：https://blog.csdn.net/justisme/article/details/100048692

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com