算法合集之《欧几里得算法的应用》

《算法合集之《欧几里得算法的应用》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、欧几里得算法的应用江苏省常州高级中学金斌∗2009年1月摘要辗转相除法求两个数的最大公约数是最早被数学家研究的算法之一，并且和数论中如连分数，丢番图方程有着紧密的联系。本文从基本的欧几里得算法谈起，涉及了几个数论问题的解法，并受其思想的启发，研究并解决了了几个看起来与数论不相关的问题。关键字：欧几里得算法辗转相除连分数Pell方程目录1欧几里得算法21.1最大公约数....................................21.1.1辗转相除......................

2、...........21.1.2复杂度分析................................21.2拓展欧几里得算法................................32另类"欧几里得算法32.1多项式.......................................42.2模意义下的矩阵行列式..............................42.3二维欧几里得算法................................52.4小结..

3、......................................73连分数和Pell方程73.1连分数.......................................73.2Pell方程......................................94另外几个其他的运用114.1两分数间分母最小的分数............................114.2有理点组成的简单多边形包含的格点数.....................125总结14ma

4、ilto:crazyb0y@126.com11欧几里得算法这一节主要是简要介绍一些关于欧几里得算法的基础，如果您对其足够了解，请直接跳过1.1最大公约数最大公约数问题是最早被研究的算法问题之一了1，并且是信息学竞赛中能涉及到的很多数论内容，比如模线性方程，模线性方程组的基础。欧几里得算法(Euclideanalgo-rithm2)，即大部分选手所知的辗转相除法"，其核心在于不断将两数规模变小，最后实现对数时间3内把问题变换到能直接判定解的规模。1.1.1辗转相除由于是数论的最基本算法，所以这里我直

5、接给出伪代码：Algorithm1EuclideanAlgorithmInput:x≥0∧y≥0Output:thegreatestcommondivisorofxandy1:whiley̸=0do2:t⇐xmody3:x⇐y4:y⇐t5:endwhile6:returnx下面简要说明一下这个算法的正确性，对于任意两个数x和y，令x=y×a+b，则对于任意d

6、x且d

7、y，有x′d=y′d×a+b，b=(x′−y′×a)×d。所以d

8、(xmody)，这说明了最后的结果ans一定是x和y的公约数。类似的

9、对于任何x和y的公约数d，都有d

10、ans，这表明了ans为最大公约数。1.1.2复杂度分析这里只给出简要的分析，说明其时间复杂度（忽略除法的复杂度）为O(logn)，对于任意两个数a;b满足a>b，我们考虑如下这个语句的效果4a⇐amodb•如果b≤a，则amodba，则amodb≤a−b

11、ean_algorithm3假设所有基本的算术运算都是O(1)的4我们忽略中间可能的模零的错误21.2拓展欧几里得算法拓展欧几里得算法（ExtendedEuclideanAlgorithm5）是基于欧几里得算法而来解一类特殊的线性丢番图方程（Diophantineequation6）ax+by=gcd(a;b)而当gcd(a;b)=1，即a;b互质的时候，这个方程的解实际上就对应了a关于模b的逆元。因此，这个算法成为解模线性方程和模线性方程组的基础，而在信息学竞赛中广泛传播。还是先给出伪代码：Alg

12、orithm2ExtendedEuclideanAlgorithmInput:a;bOutput:asolutiontoax+by=gcd(a;b)1:functionextendedgcd(a,b)2:ifb=0then3:return(1;0)4:else5:(x;y)⇐extendedgcd(b;amodb)6:return(y;x−(adivb)×y)7:endif下边做个简要分析，这是个修改版的辗转相除算法，是可以算出最后的gcd(a;b)的，考虑第3行，当