前言：

此文用于記錄學(xué)習(xí)過程中常用到的函數(shù)（較高效的算法）。同時歇式，對函數(shù)的原理進行描述驶悟，對于相關(guān)的更為細致的描述，可以參考文中的參考材失，寫的很好痕鳍，值得多看。

求最大公因子

1.迭代：

# 歐幾里得算法求兩個數(shù)字的最大公約數(shù)
# 迭代：
def gcd(a, b):
    while b != 0:
        tem = a % b
        a = b
        b = tem
    return a

2.遞歸：

# 歐幾里得算法求兩個數(shù)字的最大公約數(shù)
# 遞歸：
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

擴展歐幾里的算法（求逆元）

1.迭代：

# 擴展歐幾里的算法
def extendedGCD(a, b):
    #a*xi + b*yi = ri
    if b == 0:
        return (1, 0, a)
    #a*x1 + b*y1 = a
    x1 = 1
    y1 = 0
    #a*x2 + b*y2 = b
    x2 = 0
    y2 = 1
    while b != 0:
        q = a // b
        #ri = r(i-2) % r(i-1)
        r = a % b
        a = b
        b = r
        #xi = x(i-2) - q*x(i-1)
        x = x1 - q*x2
        x1 = x2
        x2 = x
        #yi = y(i-2) - q*y(i-1)
        y = y1 - q*y2
        y1 = y2
        y2 = y
    return(x1, y1, a)

個人覺得不太好理解龙巨，可以通過下面列表計算來輔助理解：
定理：

公式：

列表記錄計算過程：

解釋：
剛開始時笼呆，代碼中的x1,y1代表表中x-2,y-2; x2,y2代表x-1,y-1 ; a,b分別代表表中r-2,r-1 此例經(jīng)過三次迭代，b即為0恭应，此時抄邀，x1,y1正好對應(yīng)x1,y1,即-5,6（可以自己算一遍就好理解了，平時手動算時都比較喜歡這種昼榛，不容易出錯境肾。而且，通過列表計算后胆屿，同時也驗證了上面的推導(dǎo)因為 a*x + b*y = gcd(a, b)即有奥喻，a*xi + b*yi = ri （中間的每一步），從而理解推導(dǎo)過程）

2.遞歸：
基礎(chǔ)：給出任意a, b非迹，必有ax + by = gcd(a, b)环鲤。
因為gcd(a, b) = gcd(b, a mod b)，所以一個簡單實現(xiàn)是利用gcd算法算出gcd(a, b)再倒回去算 x 和 y 憎兽。

# 擴展歐幾里的算法
def extendedGCD1(a, b):
    if b == 0:
        return (1, 0, a)
    (x, y, r) = extendedGCD1(b, a%b)
    """
    gcd(a, b) = a*xi + b*yi
    gcd(b, a %  b) = b*xi+1 + (a - [a/b]*b)*yi+1
    gcd(a, b) = gcd(b, a %  b)   =>   a*xi + b*yi = a*yi+1 + b*(xi+1 - [a/b]*yi+1)
    xi = yi+1
    yi = xi+1 - [a/b]*yi+1
    """
    tmp = x
    x = y
    y = tmp - (a//b) * y
    return (x, y, r)

1. 歐幾里得算法與擴展歐幾里得算法

快速冪取模

1.這次又花了點時間看這個算法冷离，之前會但是不夠清晰吵冒，導(dǎo)致自己寫是老出問題。
主要需要明白：

• 積的取余等于取余的積的取余西剥，即

  
  

• 分奇偶兩種情況痹栖，如果是奇數(shù)，要多求一步瞭空，可以提前算到s中

  
  

2.迭代實現(xiàn):

# 快速冪取模算法
# 迭代：
def power(a, b, c):
    s = 1
    a %= c
    while b != 0:
        if b % 2 == 1:
            s = (s * a) % c
        b = b // 2
        a = (a * a) % c
    return s

可參考：

1. 快速冪取模
2. 快速冪取模算法
3. 簡單的快速冪算法（算法中存在的問題）