扩展的欧几里得算法求乘法逆元c语言代码

以下是扩展的欧几里得算法求乘法逆元的 C 语言代码：

#include <stdio.h>

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 modInverse(int a, int m) {
    int x, y;
    int gcd = extendedGCD(a, m, &x, &y);

    if (gcd != 1) {
        printf("Inverse does not exist\n");
        return -1;
    } else {
        int result = (x % m + m) % m;
        return result;
    }
}

int main() {
    int a = 10;
    int m = 17;

    int inverse = modInverse(a, m);
    printf("Inverse of %d mod %d is %d\n", a, m, inverse);

    return 0;
}

以上代码使用扩展的欧几里得算法计算给定数的乘法逆元（如果存在），并输出结果。请注意，这个算法只在两个数互质时才能求得乘法逆元。