c语言实现欧几里得算法

c语言可以使用指针来实现扩展欧几里得算法。下面是一段使用指针实现的c代码示例：

int exgcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int ret = exgcd(b, a % b, x, y);
    int t = *x;
    *x = *y;
    *y = t - a / b * (*y);
    return ret;
}

以上是欧几里得算法的实现。你可以调用这个函数，传入a、b以及x和y的指针，来得到gcd以及对应的x和y的值。

你还可以使用这个算法来解决线性同余方程。下面是一个示例代码：

int solve(int a, int b, int *x, int *y) {
    int gcd = exgcd(a, b, x, y);
    if (c % gcd == 0) {
        int k = c / gcd;
        *x *= k;
        *y *= k;
        return 1;
    } else {
        return 0;
    }
}

以上代码中，solve函数用于求解线性同余方程。你可以调用这个函数，传入a、b以及x和y的指针，来得到方程的解。如果方程无整数解，则返回0。

你还可以通过调用exgcd函数来计算逆元。下面是一个示例代码：

#include <stdio.h>
#include <string.h>

int main() {
    char code[51];
    int exgcd(int a, int b, int *x, int *y);
    int k, i, _k, y, len, gcd;

    while (scanf("%s%d", code, &k) != EOF) {
        int q = 26;
        len = strlen(code);
        gcd = exgcd(k, q, &_k, &y);
        _k = (_k % q + q) % q; //求解逆元_k

        for (i = 0; i < len; i++) {
            code[i] = (_k * (code[i] - 'A') % q) + 'A'; //逆天了！字母表顺序从0开始啊！
        }

        for (i = 0; i < len; i++) {
            printf("%c", code[i]);
        }
        printf("\n");
    }
    return 0;
}

int exgcd(int a, int n, int *x, int *y) { //扩展欧几里得算法
    if (n == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int ret = exgcd(n, a % n, x, y);
    int t = *x;
    *x = *y;
    *y = t - a / n * (*y);
    return ret;
}

以上代码中，我们使用扩展欧几里得算法来计算逆元，并将一个字符串中的字母进行加密。