python实现欧几里得算法头歌

### Python 实现欧几里得算法

为了计算两个非负整数的最大公约数 (GCD)，可以采用如下所示的欧几里得算法：

def gcd(a, b):
    if a < b:  # 确保a >= b以便简化后续逻辑处理
        a, b = b, a
    
    while b != 0:
        r = a % b
        a = b
        b = r
        
    return a  # 当b最终变为0时,a即为所求的最大公约数[^3]

# 测试案例
print(f"GCD of 48 and 18 is {gcd(48, 18)}, expected 6")  
print(f"GCD of 101 and 103 is {gcd(101, 103)}, expected 1") 
print(f"GCD of 56 and 98 is {gcd(56, 98)}, expected 14")   
print(f"GCD of 12 and 15 is {gcd(12, 15)}, expected 3")    
print(f"GCD of 0 and 25 is {gcd(0, 25)}, expected 25")     
print(f"GCD of 25 and 0 is {gcd(25, 0)}, expected 25")      

上述代码实现了基于迭代方式的经典欧几里得算法来寻找两数之间的最大公约数，并通过几个测试用例验证了其正确性。

相关问题

python实现欧几里得算法

欧几里得算法（又称辗转相除法）是求两个数的最大公约数的算法。在Python中，可以使用递归或循环实现欧几里得算法。

递归实现：

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

循环实现：

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

两个实现方式的时间复杂度都是O(log n)，其中n是a和b的最大值。

python扩展欧几里得算法

扩展欧几里得算法是一种用于求解一元线性同余方程的算法，可以表示为ax ≡ b (mod n)。在Python中，我们可以用以下函数来实现扩展欧几里得算法：

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

def solve_linear_congruence(a, b, n):
    x, y, d = extended_gcd(a, n)
    if b % d == 0:
        x0 = (x * (b // d)) % n
        for i in range(d):
            print("x ≡", (x0 + i * (n // d)) % n, "(mod", n, ")")
    else:
        print("无解")

在这段代码中，我们首先定义了一个`extended_gcd`函数，用于计算扩展欧几里得算法的结果。然后我们定义了一个`solve_linear_congruence`函数，用于解一元线性同余方程。这个函数会调用`extended_gcd`函数来得到结果，并根据情况输出方程的解或者无解情况。

通过这段代码，我们可以方便地在Python中使用扩展欧几里得算法来解决一元线性同余方程，这对于一些加密算法和数论问题来说是非常有用的。