题解 P2737 【[USACO4.1]麦香牛块Beef McNuggets】

· · 题解

这题题解竟然一个证明正确的都没有...

许多题解考虑类似小凯的疑惑使用 ab-a-b 的结论，然而这个结论只在 \gcd(a,b)=1 时适用。注意到所有数的 \gcd 为 1 不意味着存在两个数互质（比如 6,10,15），因此这个结论是不能直接套的。

考虑确定一个最大的不能被表示出来的数（如果存在）的上界。

如果所有的数的 \gcd 不为 1，那么显然是不存在最大的不能表示出来的数的（任取一个不被 \gcd 整除的数都不能被凑出来）。

设输入的所有数为 a_1\dots a_n，可以发现如果一个数 k 能凑出来，那么 k+a_1 也能凑出来；反过来说如果 k 不能凑出来，那么 k-a_1 也显然不能凑出来。

这样的话，对于任意的 i=0\dots a_1-1，一定存在一个数 f_i，使得 f_i \equiv i \pmod{a_1}，f_i 能被凑出来但是 f_i-a_1 不能（换句话说，f_i 就是 i, i+a_1, i+2a_1\dots 里面第一个能被凑出来的数）。

由于所有数的 \gcd 是 1，所以对于任意一个数 i 都能找到一串 k_1,k_2\dots k_p 使得 a_{k_1}+a_{k_2}+\dots+a_{k_p}\equiv i\pmod{a_1}，所以一定有 f_i\leq a_{k_1}+a_{k_2}+\dots+a_{k_p}。取其中最短的（p 最小的）一串 a，我们来证明 p<a_1。

如果 p\geq a_1，令 S_j=(a_{k_1}+a_{k_2}+\dots a_{k_j})\bmod a_1 即这一串 a 的前缀和，那么 0\leq S_j<a_1，因此 S_j 只有 a_1 中取值方式。根据鸽巢原理，S_0,S_1\dots S_{a_1} 中必定有两个相等，记为 S_l,S_r，那么将 a_{l+1},a_{l+2}\dots a_r 从这一串 a 中去掉，可以发现剩下的 a 的和仍然 \equiv i\pmod{a_1}，与我们选择了最小的 p 不符。

因此 p<a_1，f_i\leq a_{k_1}+\dots+a_{k_p}\leq p\times\max{a}\leq (a_1-1)\times\max{a}。

如果 t 是某个不能凑出来的数，那么显然 t\leq f_{t\bmod a_1}-a_1\leq (a_1-1)\times\max{a}-a_1，于是 t 的上界不超过 255\times256-256。

接下来就可以直接背包计算这个上界以下所有的数能不能被凑出来了。代码十分简单，就不贴了qaq。