• 正在加载中...
  • GCD”是个多义词,全部含义如下:

    纠错 | 编辑多义词

    GCD[最大公约数]

    GCD作为缩写意义有多种。它通常表示最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf)。

    编辑摘要

    基本信息 编辑信息模块

    中文名: GCD[最大公约数 英文名: hcf

    目录

    (图)GCDGCD

    最大公约数(greatest common divisor,简写为gcd;或highest common factor,简写为hcf),指某几个整数共有因子中最大的一个。有时作为共产党的拼音缩写,在网络语言中出现。是一些不法分子为了躲避监察过滤而使用。

    简介/GCD[最大公约数] 编辑

    拼音:zuì dà gōng yuē shù
    英语:greatest common divisor

    (图)GCD欧几里得

    早在公元前300年左右,欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法使用到的原理很聪明也很简单,假设用f(x, y)表示x,y的最大公约数,取k = x/y,b = x%y,则x = ky + b,如果一个数能够同时整除x和y,则必能同时整除b和y;而能够同时整除b和y的数也必能同时整除x和y,即x和y的公约数与b和y的公约数是相同的,其最大公约数也是相同的,则有f(x, y)= f(y, y % x)(y > 0),如此便可把原问题转化为求两个更小数的最大公约数,直到其中一个数为0,剩下的另外一个数就是两者最大的公约数。

    例如,12和30的公约数有:1、2、3、6,其中6就是12和30的最大公约数。

    两个整数的最大公约数主要有两种寻找方法:

    * 两数各分解质因子,然后取出同样有的项乘起来
    * 辗转相除法(扩展版)

    和最小公倍数(lcm)的关系:gcd(a, b)×lcm(a, b) = ab

    两个整数的最大公因子可用于计算两数的最小公倍数,或分数化简成最简分数

    两个整数的最大公因子和最小公倍数中存在分配律:

    * gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c))
    * lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c))

    在座标里,将点(0, 0)和(a, b)连起来,通过整数座标的点的数目(除了(0, 0)一点之外)就是gcd(a, b)

    求最大公约数/GCD[最大公约数] 编辑

    1、欧几里德算法和扩展欧几里德算法

    欧几里德算法
    欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理:

    定理: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)的公约数是一样的,其最大公约数也必然相等,得证

    欧几里德算法就是根据这个原理来做的,其算法用C++语言描述为:

      void swap(int & a, int & b)
      {
          int c = a;
          a = b;
          b = c;
      }
      int gcd(int a,int b)
      {
          if(0 == a )
          {
              return b;
          }
          if( 0 == b)
          {
              return a;
          }
          if(a > b)
          {
              swap(a,b);
          }
          int c;
          for(c = a % b ; c > 0  ; c = a % b)
          {
              a = b;
              b = c;
          }
          return b;
      }

    2、Stein算法
    欧几里德算法是计算两个数最大公约数的传统算法,他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷,这个缺陷只有在大素数时才会显现出来。

    考虑现在的硬件平台,一般整数最多也就是64位,对于这样的整数,计算两个数之间的模是很简单的。对于字长为32位的平台,计算两个不超过32位的整数的模,只需要一个指令周期,而计算64位以下的整数模,也不过几个周期而已。但是对于更大的素数,这样的计算过程就不得不由用户来设计,为了计算两个超过64位的整数的模,用户也许不得不采用类似于多位数除法手算过程中的试商法,这个过程不但复杂,而且消耗了很多CPU时间。对于现代密码算法,要求计算128位以上的素数的情况比比皆是,设计这样的程序迫切希望能够抛弃除法和取模。

    Stein算法由J. Stein 1961年提出,这个方法也是计算两个数的最大公约数。和欧几里德算法不同的是,Stein算法只有整数的移位和加减法,这对于程序设计者是一个福音。

    为了说明Stein算法的正确性,首先必须注意到以下结论:

    gcd(a,a) = a,也就是一个数和他自身的公约数是其自身
    gcd(ka,kb) = k gcd(a,b),也就是最大公约数运算和倍乘运算可以交换,特殊的,当k=2时,说明两个偶数的最大公约数必然能被2整除

    C++/java 实现
    // c++/java stein 算法
    int gcd(int a,int b){
       if(a<b)//arrange so that a>b{
           int temp = a;
           a = b;
           b=temp;
       }
       if(0==b)//the base case
           return a;
       if(a%2==0 && b%2 ==0)//a and b are even
           return 2*gcd(a/2,b/2);
       if ( a%2 == 0)// only a is even
           return gcd(a/2,b);
       if ( b%2==0 )// only b is even
           return gcd(a,b/2);

       return gcd((a+b)/2,(a-b)/2);// a and b are odd

    添加视频 | 添加图册相关影像

    开放分类 我来补充

    互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。未经许可,禁止商业网站等复制、抓取本站内容;合理使用者,请注明来源于www.baike.com。

    登录后使用互动百科的服务,将会得到个性化的提示和帮助,还有机会和专业认证智愿者沟通。

    互动百科用户登录注册
    此词条还可添加  信息模块

    WIKI热度

    1. 编辑次数:7次 历史版本
    2. 参与编辑人数:5
    3. 最近更新时间:2015-08-21 11:29:54

    相关词条

    互动百科

    扫码下载APP