不定方程求解 - C++ 代码实现
不定方程求解 - C++ 代码实现
本文介绍如何使用 C++ 代码求解不定方程 ax+by=c 的非负整数解组数。
问题描述
给定正整数 a,b,c。求不定方程 ax+by=c 关于未知数 x 和 y 的所有非负整数解组数。
输入描述
一行,包含三个正整数 a,b,c,两个整数之间用单个空格隔开。每个数均不大于 1000。
输出描述
一个整数,即不定方程的非负整数解组数。
代码实现
#include <iostream>
using namespace std;
int gcd(int a, int b) {
if (b == 0) {
return a;
} else {
return gcd(b, a % b);
}
}
int main() {
int a, b, c;
cin >> a >> b >> c;
int g = gcd(a, b);
if (c % g != 0) {
cout << 0 << endl;
return 0;
}
int x = 0, y = 0, count = 0;
while (x * a <= c) {
if ((c - x * a) % b == 0) {
y = (c - x * a) / b;
count++;
}
x++;
}
cout << count << endl;
return 0;
}
代码解释
代码首先使用欧几里得算法求解 a 和 b 的最大公约数 g。如果 c 不能被 g 整除,则方程无解,输出 0。否则,代码使用枚举法遍历 x 的所有可能取值,对于每个 x,判断 (c - x * a) 是否能被 b 整除,如果是,则该 x 对应一个解,解的个数加 1。最后输出解的个数。
总结
本文介绍了如何使用 C++ 代码求解不定方程 ax+by=c 的非负整数解组数。代码简单易懂,逻辑清晰,可供参考。
原文地址: https://www.cveoy.top/t/topic/qiNH 著作权归作者所有。请勿转载和采集!