数学是计算机程序设计的灵魂。利用数学方面的知识、数学分析的方法以及数学题解的技巧，可以使得程序设计变得轻松、美观、高效，而且往往能反映出问题的本质。在各项程序设计比赛（比如，ACM、NOI）活动中，越来越多地用到各种复杂的数学知识，对选手的数学修养要求越来越高。今天奥而思燕老师就带大家来回顾一下信息学竞赛中考核到的数学相关基础知识之【最大公约数】

最大公约数

一般地，设a₁，a₂，a₃…a_k是k个非零整数，如果存在一个非零整数d，使得d|a₁,d|a₂,d|a₃…＂d|a_k，那么d就称为a₁，a₂，a₃…a_k的公约数。公约数中最大的一个就称为最大公约数，记为GCD（a₁，a₂,a₃…a_k），显然它是存在的，至少为1。当GCD＝1时，称这n个数是互质的或既约的。公约数一定是最大公约数的约数。

一般地，设a₁，a₂，a₃，…a_k是k个非零整数，如果存在一个非零整数d，使得a1|d，a₂ld，a₃ld，…a_k|d，那么d就称为a₁，a₂，a₃，…a_k的公倍数。公倍数中最小的一个就称为最小公倍数，记为LCM（a₁，a₂，a₃，…a_k），显然它也是存在的。公倍数一定是最小公倍数的倍数。

辗转相除法

辗转相除法用来求两个数的最大公约数，又称欧几里得算法，其原理就是：GCD（x，y）＝GCD（x，y－x）。

原理的证明如下：

设z|x，z|y，则z|（y－x）。

设z不是x的因子，则z不是x，y－x的公因子。

设z|x，z不是y的因子，则z不是x，y-x的公因子。

代码实现如下：

int GCD(int x, int y) {

return y==0? x: GCD(y, x%y)；

}

二进制算法

如果想要进一步提高GCD的效率，可以通过不断去除因子2来降低常数，这就是所谓的“二进制算法”。

（1）若x，y均为偶数，则GCD（x，y）＝2*GCD(x/2,y/2);

（2）若x为偶数，y为奇数，则GCD（x，y）＝GCD（x/2,y）；

（3）若x为奇数，y为偶数，则GCD（x，y）＝GCD（x,y/2）；

（4）若x,y均为奇数，则GCD（x，y）＝GCD（x－y,y）。

代码实现如下：

inline int GCD(int x, int y){

int i,j;

if(x==0)return y;

if(y==0) return x;

for(i=0;0==(x&1);++i)x>>=1／去掉所有的2

for(j=0;0==(y&1);++j)y>>=1／／去掉所有的2

if(j

while(1){

If(x＜y）x^＝y，y^＝x，x^＝Y；／若x＜y交换x，y

if(0==(x-=y)) return y<<i;< p="">

//若x＝＝y，gcd＝＝x＝＝y（就是在辗转减， while（1）控制）

while（0＝＝（x&1）x＞＞＝1；／去掉所有的2

最小公倍数

求两个数的最小公倍数可以使用“逐步倍增”法，如求3和8的最小公倍数，可以让n从1开始逐步加1，不断检查8*n是不是3的倍数，直到n=3时，8*3=24是3的倍数了，还可以直接使用以下定理来求解。

定理:a、b两个数的最大公约数乘以它们的最小公倍数就等于a和b本身的乘积。

比如，要求3和8的最小公倍数,则LCM(3,8)=3*8 div GCD（3,8）=24

扩展欧几里得算法

扩展欧几里德算法是用来在已知(a,b)时,求解一组(p,q)，使得 p*a+q*b=GCD(a,b)。

首先，根据数论中的相关定理，解一定存在。

其次,因为GCD(a,b)= GCD(b,a%b)，所以p*a+q*b=GCD(a,b)= GCD(b,a%b)=p*b+q*a%b=p*b+q*(a-a/b*b)=q*a+(P-a/b*q)*b,这样它就将a 与b的线性组合化简为b与a %b的线性组合。

根据前边的结论:a和b都在减小，当b减小到0时，就可以得出p=1,q=0。然后递归回去就可以求出最终的p和q了。

代码实现如下:

#include＜ stdio.h＞  //形如ax＋by＝GCD（a，b）

int extended _gcd(int a, int b, int &x, int &y){

int ret, tmp;

if ( !b)(

x=1;

y=0;

return a;

}

ret-extended_gcd(b, a% b, x, y);

tmp = x;

x=y;

y= tmp-a/b * y;

return ret;

}

int main() {

Int  a, b, x, y, z;

scanf(“%d%d”,&a, &b);

z= extended_ gcd(a, b, x, y);

printf（＂%d%d%dn＂，z，x，y）;

return 0;

}

求解线性同余方程

定理1：对于方程a*x＋b*y＝c，该方程等价于a*x＝c（mod b），有整数解的充分必要条件是：c％GCD（a，b）＝0。

根据定理1，对于方程a＊x＋b*y＝c，我们可以先用扩展欧几里德算法求出一组x₀，y₀,也就是a*x₀＋b*y₀＝GCD（a，b），然后两边同时除以GCD（a,b），再乘以c。这样就得到了方程 a*x₀*c／GCD（a，b）＋b*y₀*c／GCD（a，b）＝c，我们也就找到了方程的一个解

定理2：若GCD(a，b）＝1，且x₀,y₀为a*x+b*y=c的一组解，则该方程的任一解可表示为：x=x₀+b*t，y=y₀-a*t,且对任一整数，皆成立。

根据定理2，可以求出方程的所有解。但实际问题中，我们往往被要求去最小整数解，也就是求一个特解x，t＝ b／GCD（a，b），x＝（x％t＋t）%t。

代码实现如下：

int Extended_Euclid(int a, int b, int& x, int &y)(

if(b==0){

x=1  ;

y=0 ;

return a;

}

int d=Extended_Euclid(b, a %b, x, y);

int temp =x ; x=y ; y=temp-a/b*y;

return d;

}

//用扩展欧几里得算法解线性方程ax＋by＝c;

bool linearEquation(int a, int b, int c, int& x, int &y){

int d= Extended_Euclid(a, b, x, y);

if(c%d) return false;

int k=c/d;

x*＝k；//＋t*b;

y*＝k；／／-t*a;

//求的只是其中一个解

return true;

} 

--end--

声明：本文章由网友投稿作为教育分享用途，如有侵权原作者可通过邮件及时和我们联系删除：freemanzk@qq.com