当前位置：首页 > news >正文

第十一天：不定方程求解

news 2025/7/30 10:49:14

每日一道C++题：不定方程求解

问题：给定正整数a，b，c。求不定方程 ax+by=c 关于未知数x和y的所有非负整数解组数。
要求：输入一行，包含三个正整数a，b，c，两个整数之间用单个空格开，每个数均不大于1000。输出一个整数，即不定方程的非负整数解组数。

求解不定方程的核心思路——枚举与优化

暴力枚举的原始思路：
因为 x 和 y 都是非负整数，所以对于 x 来说，它的取值范围可以初步确定为 0 =<x =<c / a （当 y = 0 时， x 能取到的最大值）；同理， y 的取值范围是 0 =<y =< c / b （当 x = 0 时）。最直接的做法就是遍历 x 所有可能的取值，然后对于每个 x ，计算 c - ax 看是否能被 b 整除，且得到的 y = (c - ax) / b 也是非负整数。

例如题目中的输入样例 2 3 18 ， a = 2 ， b = 3 ， c = 18 。 x 的可能取值是 0 到 18/2 = 9 。当 x = 0 时， 18 - 20 = 18 ， 18 / 3 = 6 ， y = 6 是整数且非负，这是一个解；当 x = 3 时， 18 - 23 = 12 ， 12 / 3 = 4 ， y = 4 有效，以此类推，遍历完所有 x 后统计符合条件的解的个数。

枚举的优化方向：
上述暴力枚举在 a 很小（比如 a = 1 ）且 c 很大（比如 c = 10^9 ）时，会导致循环次数极大，效率极低。所以后续我们可以结合数论知识（像贝祖定理、通解公式）来优化，减少不必要的枚举。对于 x ，其可能的最大值为 c // a （当 y = 0 时）；对于 y ，其可能的最大值为 c // b （当 x = 0 时）。这样可以减少不必要的枚举。

#include <iostream>
using namespace std;int main() {int a, b, c;cin >> a >> b >> c;int count = 0;// 枚举x的可能取值，x是非负整数，最大可能为c/a（当y=0时）for (int x = 0; x <= c / a; ++x) {// 计算剩余需要由by满足的值int remainder = c - a * x;// 检查remainder是否能被b整除，且y是非负整数if (remainder >= 0 && remainder % b == 0) {int y = remainder / b;// 确保y是非负整数if (y >= 0) {++count;}}}cout << count << endl;return 0;
}

通过 for 循环枚举 x 的可能取值，范围是从 0 到 c // a （确保 ax 不超过 c ）。对于每个 x ，计算剩余需要满足的值 remainder = c - a * x 。检查 y 的合法性：如果 remainder 是非负的，并且能被 b 整除，则计算对应的 y 值，并检查 y 是否为非负整数。统计解的个数：如果找到合法的 y ，则增加解的计数器 count 。

问题拓展

贝祖定理

核心结论：
不定方程 ax + by = c 有解的充要条件是 gcd(a, b) |c （即 c 是 a 和 b 最大公约数的倍数）。

在原问题基础上，先判断是否有解，再输出解的个数。

#include <iostream>
using namespace std;// 欧几里得算法求最大公约数
int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}int main() {int a, b, c;cin >> a >> b >> c;int g = gcd(a, b);// 先判断是否有解if (c % g != 0) {cout << 0 << endl; // 无解return 0;}// 有解时，转化为等价方程a /= g;b /= g;c /= g;int count = 0;// 枚举x的可能取值，注意范围变化for (int x = 0; x <= c / a; ++x) {int remainder = c - a * x;if (remainder >= 0 && remainder % b == 0) {int y = remainder / b;if (y >= 0) {++count;}}}cout << count << endl;return 0;
}

让代码更严谨，避免无效枚举（比如输入 a=2, b=4, c=5 时直接判断无解）。

通解公式与解的结构

不定方程的通解可表示为：
若 (x0, y0) 是一组特解，则所有解为：
x = x0 + b/gcd(a,b) *t
y = y0 - a/gcd(a,b) * t
（ t 为整数，需保证 x >=0, y >=0 ）
扩展欧几里得算法不仅能求最大公约数，还能找到满足 ax + by = gcd(a,b) 的一组整数解 (x0, y0) 。当原方程 ax + by = c 有解时（即 gcd(a,b) | c ），我们可以先将方程两边除以 gcd(a,b) 得到等价方程，再利用扩展欧几里得算法找到特解，然后通过乘以相应系数得到原方程的特解。
扩展题目：输出所有非负整数解的具体形式（不止个数，还要列出 (x,y) 对）。

#include <iostream>
#include <vector>
using namespace std;int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}// 扩展欧几里得算法求特解
void extendedGcd(int a, int b, int& g, int& x0, int& y0) {if (b == 0) {g = a;x0 = 1;y0 = 0;} else {extendedGcd(b, a % b, g, y0, x0);y0 -= (a / b) * x0;}
}int main() {int a, b, c;cin >> a >> b >> c;int g = gcd(a, b);if (c % g != 0) {cout << 0 << endl;return 0;}a /= g;b /= g;c /= g;int x0, y0;extendedGcd(a, b, g, x0, y0); // 求特解// 特解调整到非负（通解的基础）x0 *= c;y0 *= c;vector<pair<int, int>> solutions;// 通解参数t的范围：保证x>=0, y>=0int t_min, t_max;// x = x0 + b*t >= 0t_min = ceil((-x0) / (double)b);// y = y0 - a*t >= 0t_max = floor(y0 / (double)a);for (int t = t_min; t <= t_max; ++t) {int x = x0 + b * t;int y = y0 - a * t;if (x >= 0 && y >= 0) {solutions.emplace_back(x, y);}}// 输出解的个数和具体解cout << solutions.size() << endl;for (auto& p : solutions) {cout << "(" << p.first << ", " << p.second << ")" << endl;}return 0;
}

从“计数”升级到“找所有解”，理解不定方程解的结构。

数学推导优化

利用通解公式，直接计算 t 的范围，避免枚举 x ：

用扩展欧几里得找到特解 (x_0, y_0) 。
推导 t 的取值范围，使得 x \geq 0, y \geq 0 。
解的个数 = t_{\text{max}} - t_{\text{min}} + 1 （若有解）。

#include <iostream>
#include <cmath>
using namespace std;int gcd(int a, int b) {while (b != 0) {int temp = b;b = a % b;a = temp;}return a;
}void extendedGcd(int a, int b, int& g, int& x0, int& y0) {if (b == 0) {g = a;x0 = 1;y0 = 0;} else {extendedGcd(b, a % b, g, y0, x0);y0 -= (a / b) * x0;}
}int main() {int a, b, c;cin >> a >> b >> c;int g = gcd(a, b);if (c % g != 0) {cout << 0 << endl;return 0;}a /= g;b /= g;c /= g;int x0, y0;extendedGcd(a, b, g, x0, y0);x0 *= c;y0 *= c;// 计算t的范围// x = x0 + b*t >= 0 --> t >= ceil( (-x0)/b )// y = y0 - a*t >= 0 --> t <= floor( y0/a )int t_min = ceil( (-x0) / (double)b );int t_max = floor( y0 / (double)a );// 解的个数int count = 0;if (t_min <= t_max) {count = t_max - t_min + 1;}cout << count << endl;return 0;
}