【GESP二级】不定方程求解暂无标签时间限制：CC++ 1000MS其他语言 2000MS内存限制：CC++ 256MB其他语言 512MB难度：中等出题人：描述给定正整数abc。求不定方程 ax+by=c关于未知数x和y的所有非负整数解组数。输入描述一行包含三个正整数abc两个整数之间用单个空格隔开。每个数均不大于1000。输出描述一个整数即不定方程的非负整数解组数。用例输入 1 2 3 18用

解题思路： 根据裴蜀定理，对于不定方程ax+by=c，当且仅当c是a和b的最大公约数的倍数时，方程有整数解。 因此，首先需要计算a和b的最大公约数，然后判断c是否是最大公约数的倍数。 若是最大公约数的倍数，则存在整数解。 接下来，可以使用枚举的方法，遍历x的取值范围[0, c/a]，计算y的取值，判断是否满足方程。统计满足方程的组数即可。

具体步骤如下：

1. 读入a、b、c三个整数。
2. 计算a和b的最大公约数gcd。
3. 判断c是否是gcd的倍数，若不是则输出0，结束程序。
4. 初始化解的个数count为0。
5. 使用循环遍历x的取值范围[0, c/a]，对于每个x，计算y的取值为(c-a*x)/b。 判断y是否为非负整数，若是则count加一。
6. 输出count，即为不定方程的非负整数解组数。

代码实现如下：

#include using namespace std;

int main() { int a, b, c; cin >> a >> b >> c;

// 计算最大公约数
int gcd = 0;
for (int i = 1; i <= a && i <= b; i++) {
    if (a % i == 0 && b % i == 0) {
        gcd = i;
    }
}

// 判断c是否是gcd的倍数
if (c % gcd != 0) {
    cout << 0 << endl;
    return 0;
}

// 遍历x的取值范围，计算y的取值并判断是否满足方程
int count = 0;
for (int x = 0; x <= c / a; x++) {
    int y = (c - a * x) / b;
    if (y >= 0 && a * x + b * y == c) {
        count++;
    }
}

cout << count << endl;
return 0;