丢番图方程c语言114,丢番图方程的实现

丢番图方程（Diophantine equation）是指形如ax+by=c的整数解，其中a、b、c为已知整数，x、y为未知整数。以下是一个实现丢番图方程的C语言代码示例：

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main() {
    int a, b, c, x, y;
    scanf("%d %d %d", &a, &b, &c);
    int g = gcd(a, b);
    if (c % g != 0) {
        printf("No solution.\n");
        return 0;
    }
    a /= g;
    b /= g;
    c /= g;
    int k = 1;
    if (a < 0) {
        k = -k;
        a = -a;
    }
    if (b < 0) {
        k = -k;
        b = -b;
    }
    int p = 0, q = 0;
    while (1) {
        int t = (c - a * p) / b;
        if (t < q) {
            break;
        }
        if (a * (p + t) + b * (q + t) == c) {
            x = k * (p + t);
            y = k * (q + t);
            printf("x=%d, y=%d\n", x, y);
            return 0;
        }
        q++;
    }
    printf("No solution.\n");
    return 0;
}

该程序首先读入a、b、c三个整数，然后计算出它们的最大公约数g。如果c不能被g整除，则方程无整数解，输出"No solution."。否则，将a、b、c分别除以g，得到最简形式的方程。接下来，我们对a、b的正负性进行分类讨论，使得a、b非负。然后，我们枚举y的取值，计算出对应的x值，如果满足方程，则输出解。如果枚举完所有的y都没有找到解，则输出"No solution."。