歐幾里得算法

文中用 表示求模運(yùn)算, 表示整除, 比如 ,
歐幾里德算法(稱輾轉(zhuǎn)相除法)，用于計(jì)算兩個(gè)整數(shù)a, b的最大公約數(shù)gcd(a, b).
基本原理

1. 與第3條結(jié)合, 可以寫更相減損術(shù)
2. 與第3條結(jié)合, 歐幾里得算法(輾轉(zhuǎn)相除法)
3. 
4. 是點(diǎn)集 中最小的正整數(shù).
   c/c++ 實(shí)現(xiàn)的歐幾里得算法

int gcd(a, b)
{
    int temp;
    while(b)
    {
          temp = b;
          b = a % b;
          a = temp;
    }
  return a;
}

擴(kuò)展歐幾里得算法

求的整數(shù)解
因?yàn)槲也皇菍W(xué)數(shù)學(xué)的, 嚴(yán)謹(jǐn)?shù)淖C明就不寫了. 只寫一點(diǎn)簡單的推導(dǎo)

遞推公式

設(shè)





根據(jù)上式的 c++ 實(shí)現(xiàn)

void exgcd(int a, int b, int& g, int& x, int& y)
{  // 純c好像不支持引用, 可以用指針代替.
    if(!b)
    {
        g = a;
        x = 1;
        y = 0;
    }
    else exgcd(b, a % b, g, x, y);
    int t;
    t = x;
    x = y;
    y = t -(a / b) * y;
}

非遞歸算法

這個(gè)稍有些難, 仍然是
step1 .
step2.
step3. if(r==0) 結(jié)束, else繼續(xù)
step4. 去step2

初始時(shí)由上step1的定義有
第一次到step3, 如果,就是的解
step4
(1)式變?yōu)?, (3)式變?yōu)?img class="math-inline" src="https://math.jianshu.com/math?formula=ax%2Bby%3Dd" alt="ax+by=d" mathimg="1">

void exgcd(int a, int b, int& g, int& x, int& y)
{ // 可以用來求逆元
    if(!b)
    {
        x = 0;
        y = 1;
        g = a;
    }
    else
    {
          int x1, y1, q, r, t;
          x1 = y = 1; y1 = x = 0; 
          r = a % b; q = a / b;
          while(r) 
          {
              a = b;
              b = r;
              t = x1;
              x1 = x;
              x = t - q * x;
              t = y1;
              y1 = y;
              y = t - q * y;
              r = a % b;
              q = a / b;
          } 
          g = b;
    }
}