Python 破解信息学奥赛：求不定方程 ax+by=c 非负整数解组数

以下是使用 Python 解决此问题的代码： ```python def extended_euclidean(a, b): if a == 0: return (b, 0, 1) else: gcd, x, y = extended_euclidean(b % a, a) return (gcd, y - (b // a) * x, x) def count_solutions(a, b, c): gcd, x0, y0 = extended_euclidean(a, b) if c % gcd!= 0: return 0 x0 *= c // gcd y0 *= c // gcd a //= gcd b //= gcd count = 0 for x in range(0, (c // a) + 1): y = (c - a * x) // b if (c - a * x) % b == 0 and y >= 0: count += 1 return count a, b, c = map(int, input().split()) print(count_solutions(a, b, c)) ``` 这段代码首先使用扩展欧几里得算法求出一组特解，然后通过枚举计算非负整数解的组数。 ######[AI写代码神器 | 286点数解答 | 2024-11-07 11:21:21]