typestatusdateslugsummarytagscategoryiconpassword介绍欧几里德算法，又叫做辗转相除法，用于计算两个正整数a，b的最大公约数(the greatest common divisor)。计算公式证明第一步：不妨假设 ，则 ，，其中 第二步：取 ，其中，易得 也是 的因子第三步：而，即 c 也是 a mod b 的一个因子从而，结论得证代码C++版本除此之外，还可以用递归来定义此函数python版本使用math库中带的gcd函数手写GCD Scan QRCodeAuthor:SerendipityURL:https://serendipity565.netlify.app//article/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!Relate Posts背包问题拓扑排序[AHOI2018初中组] 分组深入理解C语言指针Mike and gcd problem拓展欧几里得算法拓展欧几里得算法贪心算法
