用c代码求a对26的逆元

以下是求a对26的逆元的C代码：

#include <stdio.h>

int main() {
    int a = 7; // 求7对26的逆元
    int m = 26;
    int x, y, r;
    int t1 = 0, t2 = 1;

    if (m == 1) {
        printf("The modular inverse does not exist.\n");
        return 0;
    }

    while (a > 0) {
        r = m % a;
        if (r == 0) {
            break;
        }
        x = t2 - (m / a) * t1;
        y = t1;
        t1 = x;
        t2 = y;
        m = a;
        a = r;
    }

    if (a == 1) {
        // a与m互质，逆元存在
        if (t2 < 0) {
            t2 += 26;
        }
        printf("The modular inverse of %d mod 26 is %d.\n", a, t2);
    } else {
        printf("The modular inverse does not exist.\n");
    }

    return 0;
}

这里以求7对26的逆元为例。程序的思路是用扩展欧几里得算法来求解逆元。

首先，判断m是否等于1，如果是，则说明逆元不存在，直接返回。然后，用while循环求解gcd(m, a)的值。在循环过程中，用t1和t2来记录x和y的上一次的值，以便下一次计算。求解x和y的方法是用上一次的t2和t1、m和a计算出来，然后更新t1和t2，m和a的值。当r等于0时，说明a和m的gcd为a，跳出循环。

如果a和m的gcd为1，说明a与m互质，逆元存在。此时，用扩展欧几里得算法求得的t2就是a对26的逆元。如果t2小于0，则加上26，使它在0到25之间。

最后，如果a和m的gcd不为1，则说明逆元不存在。