欧几里得算法及扩展（推导过程）欧几里得算法及扩展（推导过

欧几里得算法又称为辗转相除法，是计算两个数a,b的最大公约数基本算法，这是我们每一本C语言书上都写得知识点，但是它的原理与推导过程又是怎样来的，很多人都不一定知道，尤其是许多和我一样才接触算法的菜鸟，下面是我对欧几里得算法以及扩展的理解与认识

1.原理
Gcd ( a, b )=Gcd ( b, a%b )
2. 证明
a可以表示为 a=k*b+r 则 r = a%b
假设 d是a , b的最大公约数
则有 a%d==0b%d==0
而 r = a – k*b
因此 d 为b 和r=a%b 的最大公约数
同理依次辗转相除，将a换为b,将b换为a%b
这样a，b必定减小，
当b减小到0时，它的前一步是a%b
所以上一步的a是b的倍数，b是我们所求的最大公约数
也就是这一步的a
代码如下：

#include int gcd(int a,int b) { if( !b ) return a; gcd( b, a%b ); } int main() { inta, b; while( scanf( "%d%d" , &a, &b )!=EOF ) printf( "%d\n" , gcd( a,b )); return0; }

3. 扩展
推荐题目：http://acm.nyist.net/JudgeOnline/problem.php?pid=144
(1)原理
对于与不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数那么存在唯一的整数 x，y ，使得 gcd（a，b）=ax+by
(2)证明

为了分析方便，我们设a>b
【欧几里得算法及扩展（推导过程）】不难看出：a-b可被表示出来，且它也是gcd的倍数
因此gcd(a,b) = gcd(b,a-b) = gcd(a,a-b)
实际上如果a=n个b+余数，则可以把n个b都减去
再怎么减，都是gcd的倍数
当n足够大时：a-nb=a mod b
因此gcd(a,b)=gcd(b,a mod b)
欧几里德定理证明结束
从上边证明过程可以看出a-b,a-2b,a-3b,…a-nb都可以被表示出来，且x,y都是整数解
当n足够大时：a-nb=a mod b
即 a mod b可被表示出来，且x,y为整数解
gcd(a,b)=gcd(b,a mod b)等价，且x,y都为整数解
相同子问题最终gcd都可以被表示出来
推荐题目代码：

#include int gcd(int a,int b) { if( !b ) return a; gcd( b, a%b ); } int main() { int n,x, a, b; scanf( "%d", &n ); while( n-- ) { scanf( "%d%d%d" , &a, &b, &x ); int flag = gcd (a ,b); if( !(x%flag) ) printf( "Yes\n" ); else printf( "No\n" ); } return0; }