def gcd(a, b):
    if a< b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)

創(chuàng)新互聯不只是一家網站建設的網絡公司；我們對營銷、技術、服務都有自己獨特見解，公司采取“創(chuàng)意+綜合+營銷”一體化的方式為您提供更專業(yè)的服務！我們經歷的每一步也許不一定是最完美的，但每一步都有值得深思的意義。我們珍視每一份信任，關注我們的成都網站建設、成都網站制作質量和服務品質，在得到用戶滿意的同時，也能得到同行業(yè)的專業(yè)認可，能夠為行業(yè)創(chuàng)新發(fā)展助力。未來將繼續(xù)專注于技術創(chuàng)新，服務升級，滿足企業(yè)一站式成都全網營銷推廣需求，讓再小的高端網站設計也能產生價值！

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

'''擴展歐幾里得算法是歐幾里得算法（又叫輾轉相除法）的擴展。
除了計算a、b兩個整數的大公約數，此算法還能找到整數x、y（其中一個很可能是負數）。
通常談到大公因子時, 我們都會提到一個非常基本的事實: 
給予二整數 a 與 b, 必存在有整數 x 與 y 使得
ax + by = gcd(a,b)。
有兩個數a,b，對它們進行輾轉相除法，可得它們的大公約數——這是眾所周知的。
然后，收集輾轉相除法中產生的式子，倒回去，可以得到ax+by=gcd(a,b)的整數解。'''


def Ext_Euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, d = Ext_Euclid(b, a % b)
        x, y = y, (x-(a//b)*y)
        return x, y, d


t = Ext_Euclid(56, 15)
print(t)

你是否還在尋找穩(wěn)定的海外服務器提供商？創(chuàng)新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

當前文章：python最大公約數遞歸方法與非遞歸辦法及擴展-創(chuàng)新互聯
當前地址：http://www.xueling.net.cn/article/djhojp.html