16 麦乐鸡定理

2979. 最贵的无法购买的商品

前言

「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。

这是本系列的第 16 篇题解，更多题解关注 Somnia1337@力扣。

题目描述

难度：🟡中等

标签：#数学动态规划数论

给定两个 不同的质数 primeOne 和 primeTwo，你有 无数个 面值为 primeOne 和 primeTwo 的硬币，返回 无法 用这两种硬币凑出的最大面值。

输入: primeOne=2, primeTwo=5
输出: 3
解释: 无法凑出的面值有 [1,3], 所有大于 3 的面值均可凑出

解题思路

麦乐鸡定理 (Chicken McNugget Theorem)：对任意互质的 $a,b\in {\mathbb{N}}^{+}$，无法表示为 $ax+by$ ($x,y\in \mathbb{N}$) 形式的最大整数为 $a\times b-a-b$。

证明：

由 贝祖定理 (Bézout’s Theorem)：设 $a,b$ 是不全为 $0$ 的整数，$\exists x,y\in \mathbb{Z}$，使 $ax+by=\gcd (a,b)$，其中 $\gcd$ 表示最大公约数。

导出：对 $a,b\in \mathbb{N}$ 且 $a$，$b$ 互质，$x,y\in \mathbb{N}$，$n\in \mathbb{Z}$，考察不定方程 $ax+by=n$，如果方程有解，称 $n$ 可由 $a$，$b$ 表出。

记 $C=a\times b-a-b$，由于 $a$，$b$ 互质，$C$ 必为奇数，从而有结论：$\forall n\in \mathbb{Z}$，$n$ 和 $C-n$ 中有且仅有一个可由 $a$，$b$ 表出。

也即：可表出的数字与不可表出的数字在区间 $[0,C]$ 对称，如 $0$ 可表出、$C$ 不可表出，$\forall n\in \{n\in \mathbb{Z}且n>C\}$ 可表出、负数不可表出。

复杂度

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

代码

Java

class Solution {
    public int mostExpensiveItem(int primeOne, int primeTwo) {
        return primeOne * primeTwo - primeOne - primeTwo;
    }
}

最后

更多系列「外源推文」&「生活分享」关注公众号：