每日一道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 。

問題拓展

1. 貝祖定理

核心結論：
不定方程 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 時直接判斷無解 ）。

2. 通解公式與解的結構

• 不定方程的通解可表示為：
  若 (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;
}

• 從“計數”升級到“找所有解”，理解不定方程解的結構。

3. 數學推導優化

利用通解公式，直接計算 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;
}

實際場景遷移：資源分配問題

1. 場景 1：貨幣兌換

問題描述：
用面值為 a 和 b 的硬幣，湊出金額 c ，有多少種非負整數組合？

對應模型：
ax + by = c 的非負整數解個數，直接對應本題。

2. 場景 2：任務調度

問題描述：
機器 A 每小時處理 a 個任務，機器 B 每小時處理 b 個任務，要處理 c 個任務，有多少種非負整數時間分配方案？

對應模型：
ax + by = c ，其中 x 是機器 A 的工作時間， y 是機器 B 的工作時間。