为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
USACO/nuggets
这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。
- 这是USACO Chapter 4 .1中的OI题目Beef McNuggets的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。
目录 |
[编辑] 数论的结论
只要你知道以下的数论结论，这道题就是水背包了：
有两个数p,q,且gcd(q,p)=1,则最大无法表示成px+qy（x>=0,y>=0)的数是pq-q-p（对于n>pq-q-p,都可以表示成px+qy；而pq-q-p,就无法表示成px+qy）。
而且数越多，这个值只会越小。
所以我们只需考虑小于pq-q-p的范围的最小值。对于一些无解的（全体最大公约数>1)，或无数解的（有一个‘1’），应提前判断。 其实我们可以干脆全取上界为256*256-256*2。
证明：
假设可以表示为pq-q-p
那么
px+qy=pq-q-p
p(x+1)+q(y+1)=pq
p|y+1, q|x+1
又p(x+1),q(y+1)<=pq
有(x+1=kq且y+1=(1-k)q)或(x+1=(1-k)p,且y+1=kp),k是正整数
但是x,y>=0故pq-q-p,就无法表示成px+qy
2.
(p-1)(q-1)=pq-p-q+1
对于n>pq-q-p即n>=(q-1)(p-1)
gcd(p,q)=1
对于z<min{p,q}存在a,b使得ap+bq=z
不妨设a>0>b,显然a>0
那么如果a>q,取a1=a-q,b1=b+p
那么有a1*p+b1*q=z.
如果a1>q，可以继续以得到
Ap+Bq=z,且0<|A|<q,0<|B|pq-q-p n=pq-q-p+k*min{p,q}+r r<z<min{p,q} 那么取A,B Ap+Bq=r,且0<|A|<q,0<|B|<p 不妨设A>0 n=pq-q-p+k*min{p,q}+r =(q-1)p-p+k*min{p,q}+Ap+Bq =(A-1)p+(B+q-1)p+k*min{p,q} 其中(A-1),(B+q-1)>=0 那么无论min{p,q}是p还是q，都有 对于n>pq-q-p,都可以表示成px+qy ——whx
上述论断的失败
请注意，上述证明是错误的，即便（很可能）在一切实际情形下上述上界均成立。
问题的关键在于何时可以使用最小公倍数上界。有一个重要的条件：p和q互素。很容易构造一组最大公约数为1但两两不互素的数，最简单的是：(2*3=6, 3*5=15, 5*2=10)，较接近题述上限的一组是(250, 252, 255) （该组数据运行结果为13253，仍在上述上界之内）。
[编辑] 问题分析
这是一个背包问题。一般使用动态规划求解。
一种具体的实现是：用一个线性表储存所有的节点是否可以相加得到的状态，然后每次可以通过一个可以相加得到的节点，通过加上一个输入的数求出新的可以相加得到的点。复杂度是O(N×结果)。
但是可以证明结果不会超过最大的两个数的最小公倍数（如果有的话）。参见数论。所以复杂度也是O(Na2)，完全可以接受了。
判断无限解可以按上面的方法，另外也可以算所有的数的最大公约数。如果不是1，也就是说这些数不互质，那么不被这个最大公约数整除的数一定构造不出来。当且仅当这种情况会有无限解。另外有一种不需要任何数论知识的方法是判断是不是按照每个输入的数的循环节循环，如果是的话，继续算显然不会有任何结果。
判断有没有更大的解也可以按这种方法，另外如果连续最小的数那么多个数都可以构成，也不会有更大的符合条件的解。
通过位压缩可以使程序在32位机上的运行速度快32倍（由于程序代码会变长，也可能是16倍或者更小的倍数）。这样可以相当快的解决这个问题。不过复杂度还是O(Na2)。
“可以证明结果不会超过最大的两个数的最小公倍数”。我来证明一下。
已知，不定方程 ax + by = c ( a , b > 0 且 c >= ab )存在一组整数解( x0 , y0 ) (裴蜀定理)
求证，该不定方程存在一组非负整数解 ( xn , yn ) .
证明 : 由不定方程通解式得 : xn = x0 + b * t , yn = y0 - a * t ( t 是整数 )
令 xn , yn >= 0 解出 - ( x0 / b ) <= t <= ( y0 / a )
因为 c >= a * b 即 a * x0 + b * y0 >= a * b 两边同除 a * b 得 :
y0 / a - ( - x0 / b ) >= 1
所以一定存在 整数t使得 - ( x0 / b ) <= t <= ( y0 / a ) .
所以方程一定有非负整数解. 证毕.
[编辑] 特殊情况
- 无解的情况：很显然，只有输入的N个数里有1的情况才会无解，否则1本身就是一个解，因为没办法由更大的数相加得到。
- 无限个解的情况，见上面的#问题分析。
对于这道题目，这两种情况都应该输出0。
注：如果有两个连续的数x,x+1 在序列中的话，那(x-1)*x以后的数都能通过这两个相加得到。所以如果（x-1）*x前无解，则无解!
[编辑] 相关题目及扩展
这是一道很简单的背包问题。在复杂度证明中需要少量的数论知识，不过不会数论也可以解决这个问题。
这道题相对于同在USACO这一章的两道搜索题Fence Rails（也是多个背包问题）以及Cryptcowgraphy，已经是相当简单了!
[编辑] 不用背包的其他方法
如果已经证明，在有限解的情况下，解的范围一定小于256^2的话，那么，就可以采用构造法了，最坏复杂度是（256^2)*10。
对于无限解：
- 如果输入数据中有1，为无限解。
- 如果某个大于256^2的数不能被合成，为无限解。并且可以证明，这个数字一定小于等256^2+256。
抱歉，我无法给出一个非常严谨数学证明，只有伪证明。
伪证明：设x是1~256^2中最大的一个能被合成的数，min(q[i])是输入数据中最小的一个，那么，x+min(q[i])-1就不能被合成，由于没有1.
所以，本题用构造的方法就可以解决。
TASK: nuggets LANG: PASCAL Compiling... Compile: OK Executing... Test 1: TEST OK [0.000 secs, 272 KB] Test 2: TEST OK [0.000 secs, 272 KB] Test 3: TEST OK [0.000 secs, 268 KB] Test 4: TEST OK [0.000 secs, 268 KB] Test 5: TEST OK [0.000 secs, 272 KB] Test 6: TEST OK [0.000 secs, 272 KB] Test 7: TEST OK [0.011 secs, 268 KB]
关键代码：
f[0]:=true; for i:=0 to 65536 + 256 do if f[i] then begin for j:=1 to n do f[i+a[j]] :=true; end else m:=i; if m<=65536 then writeln(m) else writeln(0);
[编辑] 参见
优化算法 这道题其实是可以做到O(N^2)。 令A1表示所有鸡块中最小的那种， 如果有连续A1个数都可以打到，那么之后所有的数都是可以达到的（每次加上A1就行了）。
设
S[ I ] = { X | X % A1 = I 且可以 X 可以达到 }
F[ I ] = MIN{ X |（ X * A1 + I ）属于S[ I ] }
如果任意F[ I ] = 0 那么表示所有数都可以被构造，就输出0啦。 如果存在F[ I ] = +OO 那么表示所有余数为I的都不可以被构造，也就输出0啦。
至于F[ I ]的求法可以使用最短路算法。 建立有向图，点分别编号为0 --- A1-1, 如果 （ I + AX ）% A1 = J ， 那么从节点I向节点J连一条有向边，距离为1. DIST[ I ] 即 F[ I ]
单源最短路算法是O(N^2)
故此算法O(N^2)
评论：
个人感觉
“”如果 （ I + AX ）% A1 = J ， 那么从节点I向节点J连一条有向边，距离为1.“”
距离应为 （I + AX） div A1
因为如果小于的话，f是不会增加的，距离应为1
另外复杂度应为O（A1*N）
[编辑] 另一种解法
我认为，可以得到的牛块，如果可以得到mod 第一个数字(不妨设它为x)，那么，也可以得到 mod x+y的(y为任意一个数字) 对于每输入一个y，就可以进行x*x次这种更新，可以保证他是对的。(x种顺序不好确定) 更新完毕后，再输入下一个 如果有一个mod x==inf，那么就是无穷解，输出0，否则直接输出其中的最大值-x就行了（注意：我们得到的是最小可行的解，不是最大不可行的）
