1.1.3 最大公约数

1.1.3 最大公约数主要内容：辗转相除法、二进制算法、最小公倍数、扩展欧几里得算法、求解线性同余方程一、 辗转相除法辗转相除法也称欧几里得算法。在稍后，我们会学到扩展欧几里得算法，其是在欧几里得算法的基础上发展的。下面给出代码，相关证明可以参考《高等代数》第一章多项式中求最大公因式的证明int gcd(int x, int y){ if (x==0) return y; if (y==0) return x; return gcd(y,x%y); }二、 二进制算法一般的辗转相除法效率较低，下面给出利用因数2优化的辗转相除法。inline int gcd(int x, int y){ if (x==0) return y; if (y==0) return x; int i,j,k; for (i=0;(x1)==0;i++) x=1;//除去x中所有因子2 for (j=0;(x1)==0;j++) y=1;//除去y中所有因子2 k = min(i,j);//算出公共因子2的次数 while(1){ if (xy) swap(x,y); if ((x-=y)==0) return yi; while ((x1)==0) x=1; //去掉冗余的因子2 } }