P3951 (同余) 小凯的疑惑
题目描述
小凯手中有两种面值的金币，两种面值均为正整数且彼此互素。每种金币小凯都有无数个。在不找零的情况下，仅凭这两种金币，有些物品他是无法准确支付的。现在小凯想知道在无法准确支付的物品中，最贵的价值是多少金币？
注意：输入数据保证存在小凯无法准确支付的商品。
解题分析
-
先假设两个值范围：\(a < b\)（\(a\)、\(b\) 为两种金币的面值）。
-
分析最浅显性质：
假设答案是 \(k\)，则存在以下关系：
\(k \neq ax + by\ (x, y \geq 0) \land k + 1 = ax + by\)
求 \(k\) 的最大值，等同于求 \(k + 1\) 的最大值 。
- 从同余形式分析：
\(k + 1 \equiv a\ (mod\ b) \quad \therefore x \leq b - 1,\ \text{max}\ x = b - 1\)
。
-
\(y\) 的最大值无法通过上述式子直接求解，因为没有上限 。
-
要求 \(k\) 无解，根据相关定理，若对 \(x, y\) 没有非负限制则一定有解，因此需让 \(x\) 或 \(y = -1\) 。
-
由于通过式子已确定 \(x\) 的上限，而无法通过式子找到 \(y\) 的上限，因此选择让 \(y = -1\) 。
-
最终结论：
\(k = ab - a - b\)
（注：文档部分内容可能由 AI 生成）