给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。 注：题目来自信息学奥赛一本通 输入格式: 只有一行，为三个用空格分隔的正整数，依次代表a，b，c。每个数均不大于1000。测试用例保证合法。 输出格式: 只有一个整数，即不定方程的非负整数解组数。 c语言

```c #include <stdio.h> // 扩展欧几里得算法 int extendedEuclidean(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1, y1; int gcd = extendedEuclidean(b, a % b, &x1, &y1); *x = y1; *y = x1 - (a / b) * y1; return gcd; } int countNonNegativeSolutions(int a, int b, int c) { int x, y; int gcd = extendedEuclidean(a, b, &x, &y); if (c % gcd!= 0) { return 0; } x *= c / gcd; y *= c / gcd; int newA = a / gcd; int newB = b / gcd; int count = 0; for (int k = 0; x + k * newB >= 0; k--) { if ((x + k * newB) >= 0 && (c - a * (x + k * newB)) % b == 0 && (c - a * (x + k * newB)) / b >= 0) { count++; } } for (int k = 1; x - k * newB <= c / a; k++) { if ((x - k * newB) >= 0 && (c - a * (x - k * newB)) % b == 0 && (c - a * (x - k * newB)) / b >= 0) { count++; } } return count; } int main() { int a, b, c; scanf("%d %d %d", &a, &b, &c); int result = countNonNegativeSolutions(a, b, c); printf("%d\n", result); return 0; } ``` [2024-11-07 11:21:58 | AI写代码神器 | 499点数解答]