用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` 函数求出模乘逆元（如果存在）并返回。在主函数中，程序要求用户输入要求模乘逆元的数和模数，并输出计算结果。