编程实现模重复平方法算法，要求输出计算过程，c语言

在C语言中，模重复平方法（Modular Multiplicative Inverse，也称作取模逆元）用于解决除法运算中余数的问题，特别是当需要找到两个整数相乘的结果等于模数除以它们两者的逆元时。下面是一个简单的函数，使用扩展欧几里得算法来计算模逆：

#include <stdio.h>

// Function to find modular multiplicative inverse using extended Euclidean algorithm
int modInverse(int a, int m) {
    int x = 0, y = 1;
    int temp, t, q;

    while (a != 0) {
        q = m / a; // 计算商
        t = m - q * a; // 更新m

        m = a; // 更新a为原来的t
        a = t; // 更新a为新的t

        t = x; // 更新x为原来的y
        x = y - q * x; // 更新x为新的y
        y = t; // 更新y为新的t
    }

    if (x < 0)
        x += m; // 如果结果小于0，加模m使得结果在0到m-1之间

    return x;
}

int main() {
    int num, modulus;
    printf("请输入一个非零整数以及模数：");
    scanf("%d %d", &num, &modulus);

    if (modulus == 0) { // 检查模数是否为0，因为0没有逆元
        printf("错误：模数不能为0.\n");
    } else if (gcd(num, modulus) != 1) { // 检查是否存在逆元
        printf("错误：%d 和 %d 互质才能有逆元.\n", num, modulus);
    } else {
        int inv = modInverse(num, modulus);
        printf("模 %d 下 %d 的逆元是 %d\n", modulus, num, inv);
        printf("计算过程:\n");
        printf("Extended Euclidean Algorithm:\n");
        printf("a: %d, b: %d, x: %d, y: %d ->\n", a: num, b: modulus, x: inv, y: 1);
        for (int i = 0; i <= 5; ++i) { // 显示前几步迭代
            printf("%d * %d + %d * %d = %d (mod %d)\n", a, x, b, y, (a*x + b*y)%modulus, modulus);
            // 这里假设每一步最多显示5步，可根据实际需求调整
            t = a;
            a = b;
            b = t - (a * x) / b; // 根据算法更新值
            x = y - (x * b) / t;
            y = b;
        }
    }

    return 0;
}

// 自己实现的gcd函数
int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

这个程序首先检查模数是否为0和是否存在逆元。然后，它计算并打印出模逆，同时展示了扩展欧几里得算法的计算过程。