写一个用辗转相除法求任意数的模乘逆元的代码

下面是用辗转相除法求任意数的模乘逆元的 Python 代码：

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    gcd, x1, y1 = gcd_extended(b % a, a)
    x = y1 - (b // a) * x1
    y = x1
    return gcd, x, y

def mod_inverse(a, m):
    gcd, x, y = gcd_extended(a, m)
    if gcd != 1:
        raise ValueError("Modular inverse does not exist")
    return (x % m + m) % m

其中，`gcd_extended` 函数用于求解两个数的最大公因数和扩展欧几里得算法中的 x、y 值，`mod_inverse` 函数用于求解任意数的模乘逆元。如果模乘逆元不存在，则会抛出 ValueError 异常。

相关问题

用c++写一个用辗转相除法求任意数的模乘逆元的代码

以下是用辗转相除法求任意数的模乘逆元的C代码：

#include <stdio.h>

int extended_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }

    int r = extended_gcd(b, a % b, y, x);
    *y -= (a / b) * (*x);

    return r;
}

int mod_inverse(int a, int m) {
    int x, y;
    int gcd = extended_gcd(a, m, &x, &y);

    if (gcd != 1) {
        printf("The inverse of %d does not exist modulo %d.\n", a, m);
        return -1;
    } else {
        return (x % m + m) % m;
    }
}

int main() {
    int a, m;
    printf("Enter a and m (separated by a space): ");
    scanf("%d %d", &a, &m);

    int inv = mod_inverse(a, m);
    if (inv != -1) {
        printf("The inverse of %d modulo %d is %d.\n", a, m, inv);
    }

    return 0;
}

该程序中的 `extended_gcd` 函数实现了扩展欧几里得算法，用于计算最大公约数和模乘逆元。 `mod_inverse` 函数则利用 `extended_gcd` 函数求出模乘逆元（如果存在）并返回。在主函数中，程序要求用户输入要求模乘逆元的数和模数，并输出计算结果。

辗转相除法求模乘逆元的c++代码

辗转相除法求模乘逆元的 C 代码如下：

#include <stdio.h>
int extgcd(int a, int b, int &x, int &y)
{
    int d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1;
        y = 0;
    }
    return d;
}
int mod_inverse(int a, int m)
{
    int x, y;
    extgcd(a, m, x, y);
    return (m + x % m) % m;
}
int main()
{
    int a = 3, m = 11;
    printf("%d 的模 %d 乘逆元为 %d\n", a, m, mod_inverse(a, m));
    return 0;
}

以上代码使用了扩展欧几里得算法求解模乘逆元。其中，`extgcd` 函数可以求解任意两个整数的最大公约数，并返回其值，同时通过引用返回参数 `x` 和 `y` 的值，满足 $ax + by = \gcd(a, b)$。`mod_inverse` 函数则使用 `extgcd` 求解模乘逆元，即 $a$ 模 $m$ 的乘法逆元 $x$，满足 $ax \equiv 1 \pmod m$，并返回其值。