第2章　不定方程与整数约束

不定方程通常不是“解出唯一未知数”，而是用整数、范围、奇偶、倍数和极值把可能性压缩到有限个。

1. 线性整数方程

若大车每辆运 $a$ 人、小车每辆运 $b$ 人，总人数 $N$，则 $ax+by=N$，其中 $x,y$ 是非负整数，分别表示两种车的辆数。因为左边一定是 $a,b$ 的公约数的倍数，先检查最大公约数：

$$gcd(a,b)\mid N$$

不满足就无整数解。例如 $6x+9y=25$ 不可能，因为左边必是 3 的倍数、右边不是。若最大公约数能整除 $N$，只说明这个必要条件通过；还要检查非负、正数、数量上限等题目限制。再对方程取余，可找出 $x$ 或 $y$ 的余数类别，把可能范围缩小后代回。

2. 线性组合的快捷解法

当 $a,b$ 接近，常用“总数换算基准法”。例如每件方案本来按较小单位计量，改用大单位会多出固定差额；用差额反推件数，通常比解二元方程快。

当题目问“最多/最少”，目标函数也要纳入：在全部整数解中，比较 $x+y$、$x-y$ 或某个所求组合，而不能只找到任意一组解。

3. 总价、不规则单价

把金额先全部换成“分”，再列整数方程。例如单价 1.70、3.00、4.00 元，总价 40.60 元，可写为 $170x+300y+400z=4060$。求总支数最大，等价于在约束下最大化 $x+y+z$。用小单价商品作基线，再看替换成更贵商品会使金额增加多少。

易错点：钱的单位不统一导致小数方程；把每个变量都允许取 0，但题干规定“每种至少一个”；找到最小可行数量后误答“最多”。