Beef McNuggets USACO 4.1（数论公约数问题+背包阵亡）

4章第一题就跪..

数论先不说，先说背包，大概意思简化为，n个数，无限取用，给你个组合上限，找到最大的不能组合的数。开始还是有点迷惑，没看懂，

后来一想貌似就是完全背包啊...

还没有完全背包的那个例子复杂...

再说数论，一个开始题目里用到这样的例子， abc 3个数，ab的最大公约=m， mc的最大公约=1，证abc最大公约数=1

其实这题可以转为证明ab的最大公约数是否一定能整出其他公约数，假设abc存在非0公约数d，那么d<m且是ab公约，可知d一定不能被m整出

若d能被m整出，又c能整出d，那么mc的最大公约！=1，条件冲突！！！

所以这里转为证明 ab的最大公约数是否一定能整出其他公约数。

ab 最大公约设为m，较小的一个公约为n

设x=a/m,y=b/m,可知gcd（x，y）=1；

又mx ，my能整出n，假设m不能整出n

那么mx，my除n时有一部分一定是要被x和y除掉的，且相同。

那么x，y有公约数，这里又冲突，所以反证得出m一定整除n。

这题还有些东西，下次整理下，先贴个仿照的代码过了再说

gcd（int a,int b）

{

if(a==0)

return b;

return gcd(b%a,a);

}

 1 /*
 2 
 3 ID: hubiao cave
 4 
 5 PROG: nuggets
 6 
 7 LANG: C++
 8 
 9 */
10 
11 
12 
13 
14 #include<iostream>
15 #include<fstream>
16 #include<cstring>
17 #include<algorithm>
18 
19 using namespace std;
20 
21 
22 int gcd(int,int);
23 
24 int main()
25 
26 {
27 
28 
29     ifstream fin("nuggets.in");
30     ofstream fout("nuggets.out");
31     int buf[11],n;
32     fin>>n;
33     for(int i=0;i<n;i++)
34         fin>>buf[i];
35     sort(buf,buf+n);
36 
37     int t=buf[0];
38     for(int i=1;i<n;i++)
39     {
40         t=gcd(t,buf[i]);
41         if(t==1)
42             break;
43     }
44     
45     if(t!=1)
46     {
47         fout<<0<<endl;
48         return 0;
49     }
50 
51     bool b[1000000];
52     memset(b,false,sizeof(b));
53     b[0]=true;
54 
55     int sumv=buf[n-2]*buf[n-1]*gcd(buf[n-2],buf[n-1]);
56     int i,j;
57 
58     for(i=0;i<n;i++)
59     {
60         for(j=buf[i];j<=sumv;j++)
61         {
62             if(b[j-buf[i]])
63                 b[j]=true;
64         }
65     }
66 
67     for( i=sumv;i>0;i--)
68     {
69         if(b[i]==false)
70         {
71             break;
72         }
73     }
74     
75     fout<<i<<endl;
76     
77     return 0;
78 
79 
80 }
81 int gcd(int A,int B)
82 {
83     if(A==0)
84         return B;
85     return gcd(B%A,A);
86 }