设 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 )...
扩展
欧几里得算法
新的改变功能快捷键合理的创建标题，有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能，丰富你的文章UML 图表FLowchart流程图导出与导入导出导入
你好！ 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章，了解一下Markdow
本文是参考新浪博客而写。
欧几里得算法
, 又称辗转相除法, 用于求两个自然数的最大公约数. 算法的思想很简单, 基于下面的数论等式
gcd(a, b) = gcd(b, a mod b)
其中gcd(a, b)表示a和b的最大公约数, mod是模运算, 即求a除以b
求最大公约数的最常用的算法是
欧几里得算法
,也称为辗转相除法。问题定义为求i和j的最大公约数gcd(i,j),其中i和j是整数,不妨设i>j。算法可以递归的表示:
1.如果j能整除i,那么gcd(i,j)=j;
2.j不能整除i,令r=i%j,那么gcd(i,j)=gcd(j,r).
上面的算法对于i<j的情况也是可以的，实际上是做了一次交换。
使用C语...
