扩展欧几里得算法的代码

下面是扩展欧几里得算法的 Python 代码实现：

def extended_euclidean_algorithm(a, b):
    """
    使用扩展欧几里得算法计算a和b的最大公约数g以及一组整数x和y，满足ax + by = g
    :param a: 整数a
    :param b: 整数b
    :return: 最大公约数g和一组整数x和y，满足ax + by = g
    """
    if b == 0:
        return a, 1, 0
    else:
        g, x1, y1 = extended_euclidean_algorithm(b, a % b)
        x, y = y1, x1 - (a // b) * y1
        return g, x, y

这个函数接受两个整数 `a` 和 `b` 作为输入，并返回最大公约数 `g` 以及一组整数 `x` 和 `y`，满足 `ax + by = g`。

相关问题

c++扩展欧几里得算法代码

以下是使用C++实现的扩展欧几里得算法的示例代码：

#include <iostream>

// 扩展欧几里得算法
int extendedGCD(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    int x1, y1;
    int gcd = extendedGCD(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;

    return gcd;
}

// 测试代码
int main() {
    int a = 56;
    int b = 15;
    int x, y;
    int gcd = extendedGCD(a, b, x, y);

    std::cout << "GCD(" << a << ", " << b << ") = " << gcd << std::endl;
    std::cout << "贝祖等式: " << gcd << " = " << x << "*" << a << " + " << y << "*" << b << std::endl;

    return 0;
}

运行此代码，将输出：

GCD(56, 15) = 1
贝祖等式: 1 = -4*56 + 15*15

这个例子演示了如何使用扩展欧几里得算法计算56和15的最大公约数，并输出它们的贝祖等式。

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中使用扩展欧几里得算法来解决一元线性同余方程，这对于一些加密算法和数论问题来说是非常有用的。