posts - 195, comments - 34, trackbacks - 0, articles - 1

          最大公約數和最小公倍數

          Posted on 2009-10-26 22:56 小強摩羯座 閱讀(291) 評論(0)  編輯  收藏 所屬分類: 算法編程

          最大公約數和最小公倍數

          語言: C, 標簽: 無  2008/07/22發布 5個月前更新 更新記錄
          作者: 半瓶墨水, 點擊5221次, 評論(0), 收藏者(0), , 打分:登錄以后才能打分, 目前平均0.0分,總分0, 共有0個用戶參與打分
          # 以下描述來自: http://baike.baidu.com/view/47637.htm
          #
          # 最大公約數(greatest common divisor,簡寫為gcd;
          # 指某幾個整數共有公約數中的最大一個
          #  例: 在2、4、6中,2就是2,4,6的最大公約數。
          #
          # 重要性質:
          # gcd(a,b)=gcd(b,a) (交換律)
          # gcd(-a,b)=gcd(a,b)
          # gcd(a,a)=|a|
          # gcd(a,0)=|a|
          # gcd(a,1)=1
          # gcd(a,b)=gcd(b, a mod b)
          # gcd(a,b)=gcd(b, a-b)
          # 如果有附加的一個自然數m,
          # 則: gcd(ma,mb)=m * gcd(a,b) (分配率)
          # gcd(a+mb ,b)=gcd(a,b)
          # 如果m是a和b的最大公約數,
          # 則: gcd(a/m ,b/m)=gcd(a,b)/m
          # 在乘法函數中有:
          # gcd(ab,m)=gcd(a,m) * gcd(b,m)
          # 兩個整數的最大公約數主要有兩種尋找方法:
          # * 兩數各分解質因子,然后取出同樣有的項乘起來
          # * 輾轉相除法(擴展版)
          # 和最小公倍數(lcm)的關系:
          # gcd(a, b) * lcm(a, b) = ab
          # a與b有最大公約數,但不一定有最小公倍數。
          # 兩個整數的最大公因子可用于計算兩數的最小公倍數,或分數化簡成最簡分數。
          # 兩個整數的最大公因子和最小公倍數中存在分配律:
          # * 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)。
          #
          #
          # 以下代碼來自: http://bbs.bccn.net/thread-224663-1-1.html
          #
          int GCD(int a, int b)
          {
             if(b == 0) return a;
             else return GCD(b, a % b);
          }

          int LCM(int a, int b)
          {
             return a * b / GCD(a,b);
          }

          /*以下代碼來自:http://en.wikipedia.org/wiki/Binary_GCD_algorithm */
          unsigned int gcd(unsigned int u, unsigned int v)
          {
              int shift;

              /* GCD(0,x) := x */
              if (u == 0 || v == 0)
                  return u | v;

              /* Let shift := lg K, where K is the greatest power of 2
                 dividing both u and v. */
              for (shift = 0; ((u | v) & 1) == 0; ++shift) {
                  u >>= 1;
                  v >>= 1;
              }

              while ((u & 1) == 0)
                  u >>= 1;

              /* From here on, u is always odd. */
              do {
                  while ((v & 1) == 0/* Loop X */
                      v >>= 1;

                  /* Now u and v are both odd, so diff(u, v) is even.
                     Let u = min(u, v), v = diff(u, v)/2. */
                  if (u < v) {
                      v -= u;
                  } else {
                      unsigned int diff = u - v;
                      u = v;
                      v = diff;
                  }
                  v >>= 1;
              } while (v != 0);

              return u << shift;
          }


          主站蜘蛛池模板: 宕昌县| 临海市| 郯城县| 芜湖市| 彩票| 富源县| 汉源县| 浮梁县| 将乐县| 余庆县| 鹿邑县| 道孚县| 鱼台县| 茂名市| 新丰县| 鲁甸县| 安乡县| 会昌县| 加查县| 克什克腾旗| 虎林市| 宜君县| 嵊州市| 康马县| 衡水市| 东明县| 东丽区| 瑞安市| 横山县| 新竹县| 吉林省| 华容县| 米易县| 江华| 体育| 卓资县| 明星| 丘北县| 古丈县| 尼玛县| 内乡县|