随笔-141  评论-9  文章-3  trackbacks-0

可以证明结果不会超过最大的两个数的最小公倍数(如果有的话, 这部分还没做)。

判断无限解可以按上面的方法,另外也可以算所有的数的最大公约数。

如果不是1,也就是说这些数不互质,那么一定没办法构成所有的不被这个最大公约数整除的数。当且仅当这种情况会有无限解。

/*
ID: lorelei3
TASK: nuggets
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int MAX = 70000;

bool f[MAX];
int n;
int a[15];

int gcd(int a, int b){
    
if(b==0)
        
return a;
    
else 
        
return gcd(b, a%b);
}


int main(){
    
int i,j,k;

    ifstream fin(
"nuggets.in");
    ofstream fout(
"nuggets.out");

    fin
>>n;

    
for(i=1; i<=n; ++i)
        fin
>>a[i];

    k
=a[1];
    
for(i=2; i<=n; ++i)
        k 
= gcd(k, a[i]);

    
if(k!=1){
        fout
<<0<<endl;
        
return 0;
    }


    f[
0]=true;

    
for(i=1; i<=n; ++i)
        
for(j=a[i]; j<=65536++j)
                f[j] = f[j]||f[j-a[i]];


    
for(i=65536; i>=1--i)
        
if(!f[i])
            
break;
    
    fout
<<i<<endl;
    
    
return 0;
}

posted on 2011-01-20 20:34 小阮 阅读(263) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理