自动搬运

查看原文

来自洛谷，原作者为

	_rqy **

搬运于2025-08-24 21:41:00，当前版本为作者最后更新于2019-07-09 11:30:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

许多题解考虑类似小凯的疑惑使用 $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。