最大公约数

 

一、辗转相除法

  

inline int GCD(int x,int y)
{
    int r=x%y;
    while(r) x=y,y=r,r=x%y;
    return y;
}

  原理证明

  • 因为a=b+c,于是b,c的公约数也必然是a的约数,假设(b,c)=e,
  • ((b,c)=e表示e为b和c的最大公约数)那么有elb+c,即ela,
  • 根据"d是b,c的公约数"知道dle,,
  • 又因为e也是a,b的公约数,eld,综上有e=d
  • 可见(a,b)=(b,c)=d

 

二、二进制算法

可将x,y分为六种情况进行讨论:

  1. 若x=0或y=0:返回y或x;
  2. 若x<y:交换x,y;
  3. 若x为偶数且y为偶数:gcd(x/2,y/2);
  4. 若x为偶数且y为奇数:gcd(x/2,y);
  5. 若x为奇数且y为偶数:gcd(x,y/2);
  6. 若x为奇数且y为奇数:gcd(x-y,y);
inline int gcd(int x,int y)
{
    int n=0,m=0;
    while(!(x&1)) ++n,x>>=1;
    while(!(y&1)) ++m,y>>=1;
    n=min(n,m);
    while(1)
    {
         if(x<y) swap(x,y);
         if(!(x-=y)) return y<<n;
         while(!(x&1)) x>>=1;
    }
} 

 

三、最小公倍数

  几个数的最小公倍数为几个数的乘积除以这几个数的最大公约数

四、扩展欧几里得

  扩展欧几里德算法是用来在已知a, b求解一组x,y,使它们满足贝祖等式(裴蜀定理,博客整除这一章有介绍): ax+by = gcd(a, b) =d(解一定存在,根据数论中的相关定理)。扩展欧几里德常用在求解模线性方程及方程组中。

  公式表述1

  • gcd(a,b)=gcd(b,a mod b)
  • 证明:a可以表示成a = kb + r,则r = a mod b
  • 假设d是a,b的一个公约数,则有
  • d|a, d|b,而r = a - kb,因此d|r
  • 因此d是(b,a mod b)的公约数
  • 假设d 是(b,a mod b)的公约数,则
  • d | b , d |r ,但是a = kb +r
  • 因此d也是(a,b)的公约数
  • 因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证

  公式表述2

  • 首先根据裴蜀定理得,解一定存在
  • 其次因为gcd(a,b)=gcd(b,a%b),所以p*a+q*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,其递归会最初的p,q就行了
//其中x,y为满足x*a+y*b=gcd(a,b)的解,ret为gcd(a,b);
int exgcd(int a,int b,int &x,int &y)
{
    int ret,temp;
    if(!b) 
    {
        x=1,y=0;
        return a;
    }
    ret=exgcd(b,a%b,x,y);
    temp=x,x=y,y=temp-a/b*y;
    return ret;
}

 

五、求解线性方程

  定理一:对于方程a*x+b*y=c,该方程等价于a*x≡c(mod) b,有整数解的充分必要条件是:c%GCD(a,b)=0。

  定理二:若GCD(a,b)=1,且x0,y0为a*x+b*y=c的一组解,则方程的任意解可以表达为  x=x0+b*t,y=y0-a*t,对于任意整数t皆成立

  根据定理一,我们可以求出方程a*x0+b*y0=gcd(a,b)的一组解,x0,y0,两边同时除以GCD(a,b)再乘以c就得到原方程的一个解

  根据定理二,我们就可以求出一组特解(最小整数解),t=b/gcd(a,b),x=(x%t+t)%t;

  

 

 

 

 

最大公约数

上一篇:求两个数的最大公约数,Euclid算法证明,以及C语言代码实现


下一篇:【程序设计与算法(一)】求最大公约数