USACO Beef McNuggets

这道题的另一个描述：a1x+a2y+a3z+...=N（其中a1,a2,a3...已知且为正整数，x,y,z...为任意自然数），求不能被“拼凑”的N的最大值。

如果这道题把答案的上限降低到2000000，每个人都可以想到用类似背包的动态规划解决这个问题。可是，题目给的是2x10^9，构造一个如此大的数组显然是不可能的。

这里就涉及到一个关于正整数的结论（摘自USACO）：Given two relatively prime numbers N and M, the largest number that you cannot make is NM - M - N, that is, the product minus the sum.这样以来，那个2x10^9就没有任何意义了，只要构造256 * 256 - 256 - 256 = 65024大的数组就足够了。

需要注意的是几个例外情况：
1）如果任何一个未知数的系数为1，那么任何自然数都可以被构造，因此输出0；
2）根据上面那个结论，如果在65024外还有数不能被构造，那么gcd(a1,a2,a3,...)>1，不能构造的N一定有无数个，因此输出0。

代码如下：

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MAX_BOX (256+3)
05 #define MXN (256 * 256)
06
07 int box[MAX_BOX];
08 _Bool available[MXN] = {};
09 int num;
10
11 void init()
12 {
13     int n,i,k;
14     _Bool origin[MAX_BOX];
15     memset(origin,0,sizeof(origin));
16     scanf("%d",&n);
17     while(n --)
18     {
19         scanf("%d",&i);
20         origin[i] = 1;
21     }
22     for(i = 1;i < MAX_BOX;i ++)     //清除输入数据中有倍数关系的数，顺带排序，可以稍微节省一些时间，不是必须的
23     {
24         if(origin[i])
25         {
26             for(k = 2;i * k < MAX_BOX;k ++)
27                 if(origin[i * k])    origin[i * k] = 0;
28         }
29     }
30     for(i = 1,num = 0;i < MAX_BOX;i ++)
31     {
32         if(origin[i])
33         {
34             //printf("%d\n",i);
35             box[num ++] = i;
36         }
37     }
38     //check for exception
39     if(origin[1])
40     {
41         printf("0\n");
42         fclose(stdout);
43         exit(0);
44     }
45 }
46
47 void solve()
48 {
49     long i,j;
50     available[0] = 1;
51     for(i = 0;i < num;i ++)
52         for(j = 0;j < MXN;j ++)
53         {
54             if(available[j] && box[i] + j < MXN)    available[box[i] + j] = 1;
55         }
56     for(i = MXN - 1;i > 0;i --)  //寻找最大的解
57         if(!available[i])
58         {
59             if(i > 256 * 256 - 256 * 2)  //有无数个不能被构造的N
60             {
61                 printf("0\n");
62                 return;
63             }
64             else
65             {
66                 printf("%ld\n",i);
67                 return;
68             }
69         }
70     printf("0\n");
71 }
72
73 int main()
74 {
75     freopen("nuggets.in","r",stdin);
76      freopen("nuggets.out","w",stdout);
77     init();
78     solve();
79     fclose(stdin);
80     fclose(stdout);
81     return 0;
82 }