DevLog

题目背景与核心痛点

这是一道广为人知的经典数论应用题，在各大算法平台上常被称为“买不到的数目”或“麦乐鸡定理（Chicken McNugget Theorem）”。

题目通常给出两个互质的打包数量 $a$ 和 $b$ （例如 4 和 7），要求找出最大那个无法通过 $a$ 和 $b$ 组合（相加）拼凑出来的正整数。如果你尝试用暴力搜索（DFS）或者完全背包（DP）去硬刷，由于你不知道搜索的“上限在哪里”，很容易导致程序超时（TLE）或陷入死循环。然而，只要我们揭开它的数论面纱，这道题完全可以用 $O(1)$ 的数学公式直接秒杀。

解题思路：从数论原理到公式秒杀

1. 为什么一定存在一个“最大买不到的数”？

根据数论中的裴蜀定理（Bézout's Identity）：如果两个正整数 $a$ 和 $b$ 互质（即 $\gcd(a, b) = 1$ ），那么对于任意整数 $z$ ，方程 $a \cdot x + b \cdot y = z$ 一定有整数解。

但是在现实生活中，“买东西”不允许出现负数（即 $x, y \ge 0$ ）。当 $z$ 足够大时，非负整数解是一定存在的；而当 $z$ 比较小时，由于不能使用负数凑数，就会出现一部分数字无法被组合出来。

2. 麦乐鸡定理（Sylvester 定理）

数学家西尔维斯特（James Joseph Sylvester）早就为我们证明了一个定理：

当两个正整数 $a, b$ 互质时，对于方程 $a \cdot x + b \cdot y = z$ ，使得方程没有非负整数解的最大正整数 $z$ 的公式为： $z = a \times b - a - b$

💡 思维深化：怎么直观理解这个上限？（同余桶理论）

我们可以把数字按模 $a$ 的余数分成 $a$ 个“桶”（剩余系）。以 $a = 4, b = 7$ 为例，我们看 $7$ 的倍数在模 4 下的分布：

$7 \times 0 = 0 \equiv 0 \pmod 4$ （此桶齐了，0 之后所有 4 的倍数都能凑出）
$7 \times 1 = 7 \equiv 3 \pmod 4$ （此桶齐了，7 之后所有余 3 的数都能凑出，如 11, 15...）
$7 \times 2 = 14 \equiv 2 \pmod 4$ （此桶齐了，14 之后所有余 2 的数都能凑出，如 18, 22...）
$7 \times 3 = 21 \equiv 1 \pmod 4$ （此桶齐了，21 之后所有余 1 的数都能凑出，如 25, 29...）

当最后一个桶（余 1 的桶）在 $21$ 被填满时，说明 $21$ 之后的所有数字都彻底安全了。而在这最后一个桶开辟（ $21$ ）之前，该桶上一个无法凑出的数就是 $21 - 4 = 17$ 。这就是公式 $a \times b - a - b$ （即 $a \times (b-1) - a$ ）在数论底层的本质逻辑。

C 语言代码实现

在实际比赛盲测中，我们需要防御输入非法边界（如负数）以及不互质的恶意数据。为了拿到绝对的满分，严谨的代码应当引入 辗转相除法（GCD） 进行前置拦截：

#include <stdio.h>

// 辗转相除法求最大公约数
long long gcd(long long m, long long n) {
    return n == 0 ? m : gcd(n, m % n);
}

int main() {
    long long a, b;
    
    // 严谨读取输入的两个包装数量
    if (scanf("%lld %lld", &a, &b) == 2) {
        
        // 防御性编程：确保输入合法且互质（GCD为1）
        if (a > 0 && b > 0 && gcd(a, b) == 1) {
            // 直接套用麦乐鸡定理公式进行计算
            long long ans = a * b - a - b;
            printf("%lld\n", ans);
        } else {
            // 如果不互质或数据非法，按题目要求输出特定错误码（如-1）
            printf("-1\n"); 
        }
    }
    
    return 0;
}

💡 蓝桥杯通关·快速复盘

一句话题眼（数学降维打击） 核心本质是 “互质数的不定方程非负整数解问题”（麦乐鸡定理/Sylvester 定理）。当 $a, b$ 互质时，最大无法拼凑的数存在固定边界。无需暴力搜索或动态规划，直接套用 $O(1)$ 公式秒杀： $\text{最大值} = a \times b - a - b$ 底层逻辑（同余桶理论）：所有数按模 $a$ 的余数分为 $a$ 个桶，利用 $b$ 的倍数将桶逐个填满。当最后一个桶在 $a \times (b-1)$ 被填满时，前一个无法填满的空缺即为最大买不到的数： $a \times (b-1) - a = a \times b - a - b$ 。
防错指南（避坑卡片）
1. 大数越界防御（极重要）：当 $a, b$ 接近 $10^5$ 时，中间计算结果 a * b 会达到 $10^{10}$ 级别，远超 int 的最大上限（约 $2 \times 10^9$ ）。为了防止在赛场上因整型溢出痛失全分，变量与相乘计算必须强制使用 long long，输出配合 %lld。
2. 前提条件拦截（不互质特判）：公式生效的绝对前提是 $\gcd(a, b) = 1$ （两数互质）。若输入不互质（如 4 和 6），最大买不到的数为无穷大。竞赛代码中必须引入**辗转相除法（GCD）**对不互质或非正数输入进行前置过滤。
3. 输入流防御：严格使用 if (scanf("%lld %lld", &a, &b) == 2) 确保双变量读入的健壮性。

无法购买的数字