整數解與不定方程（線性不定方程）

這招在解什麼題

競賽常出現這種題：未知數比方程多、而且限定整數，例如

$6x + 9y = 45,\quad -4 \le x \le 10,\ x,y \in \mathbb{Z}.$

一條方程兩個未知數，實數解有無限多組、根本「解不完」。但一旦限定 整數、再加上 範圍，符合的解就只剩有限幾組——這類「$ax+by=c$ 求整數解」的問題叫 線性不定方程（linear Diophantine equation）。

核心三步：先判有沒有解（gcd）→ 寫出所有解（通解）→ 套範圍數個數。

第一步：有沒有整數解？看 gcd 整不整除

$ax + by = c$ 有整數解 若且唯若 $\gcd(a,b)$ 能整除 $c$。

道理很直接：$ax+by$ 不論 $x,y$ 取什麼整數，一定是 $\gcd(a,b)$ 的倍數（因為 $a,b$ 都是它的倍數）。所以右邊 $c$ 若不是 $\gcd(a,b)$ 的倍數，等式根本湊不出來。

以 $6x+9y=45$ 為例：$\gcd(6,9)=3$，而 $3 \mid 45$，有解。既然三項都是 $3$ 的倍數，先兩邊同除以 $\gcd$ 化到最簡：

$2x + 3y = 15,\qquad \gcd(2,3)=1.$

化到 $\gcd=1$ 是好習慣：係數變小、通解的步長也最乾淨。

第二步：一組特解 → 通解公式

化簡到 $2x+3y=15$ 後，先湊一組明顯的解。試 $x=0$：$3y=15\Rightarrow y=5$。所以 $(x_0,y_0)=(0,5)$ 是一組特解。

接著寫通解：把化到最簡後的式子 $a'x+b'y=c$（此處 $a'=2,\ b'=3$，且 $\gcd(a',b')=1$）的所有整數解一次表達出來——

$x = x_0 + b'\,t,\qquad y = y_0 - a'\,t,\qquad t \in \mathbb{Z}.$

代進去驗證：$a'(x_0+b't)+b'(y_0-a't) = a'x_0+b'y_0 = c$，$t$ 前的項 $a'b't-a'b't$ 剛好抵銷，所以每個整數 $t$ 都給一組解、也只有這些。本例：

$x = 0 + 3t = 3t,\qquad y = 5 - 2t.$

係數對應別搞反：$x$ 加的是 $y$ 的係數 $b'=3$、$y$ 減的是 $x$ 的係數 $a'=2$（交叉的），而且一加一減。

第三步：套上範圍，數出解的個數

通解有無限多組（每個整數 $t$ 一組），題目的範圍限制才把它砍成有限。本例限制 $-4 \le x \le 10$：

$-4 \le 3t \le 10 \;\Rightarrow\; -\tfrac{4}{3} \le t \le \tfrac{10}{3} \;\Rightarrow\; t \in \{-1,0,1,2,3\}.$

$t$ 有 $5$ 個整數值，對應 $5$ 組解 $(x,y)=(-3,7),(0,5),(3,3),(6,1),(9,-1)$。數 $t$ 的整數個數，就是數解的個數。

若題目要的是正整數解，就把 $x>0$ 且 $y>0$（或 $\ge 1$）一起翻譯成對 $t$ 的不等式，取交集再數。範圍是正整數、非負、還是任意整數，會直接改變答案。

常見陷阱（很多人在這裡掉分）

• 沒先驗 gcd 就開始湊：若 $\gcd(a,b)\nmid c$，其實一組解都沒有，硬湊只是浪費時間。
• 忘記化到最簡：不除以 $\gcd$ 也能做，但步長會變成 $b/\gcd$、$a/\gcd$，容易把「相鄰兩組解差多少」算錯而多數或少數。
• 通解係數交叉搞反 / 忘了一加一減：$x=x_0+b't$、$y=y_0-a't$，寫成同號或對調係數就會漏解、重複數。
• 範圍只套在一個變數上：$x$ 有範圍不代表 $y$ 沒有——兩個變數的限制都要翻成對 $t$ 的不等式，取交集。
• 邊界的開閉沒看清：$\le$ 與 $<$、含不含 $0$，差一個就多算或少算一組。
• 「有序 vs 無序」：問「$(x,y)$ 幾組」通常是有序對；若題目其實在問無序的組合（兩種東西可對調），要另外處理，別直接套個數。

和其他技巧的關係

• $xy+ax+by$ 型不是線性的，要先用 SFFT 因式分解 配成乘積、再讀因數對——那是「乘法版」的不定方程。
• 「把 $n$ 個相同物分給幾個人、每人至少幾個」 這類分配問題，本質也是求 $x_1+x_2+\dots=n$ 的非負整數解個數，可用隔板法或系統列舉。
• 三元以上（如 $3x+5y+8z=40$、各至少 $1$）通常固定一個變數、逐一列舉，退回成一個個二元不定方程來解。

學完動手

判 gcd、寫通解、套範圍——這套流程要靠多做幾題才會變成反射動作。到練習題庫做本知識點的原創分層練習，每題附完整繁中詳解。