PKU 3456 Frobenius
http://poj.org/problem?id=3456
最大公約数が1であるような4つの整数a1,a2,a3,a4が与えられる。
この時、w1*a1+w2*a2+w3*a3+w4*a4 (wiは0以上の整数) の形で表せない1000000以下の数字の個数と、この形式で表せない数字のうち最大のものが1000000以下であればそれを出力しろというような問題。
多項式で表せるものを全列挙する。
そのあと、この形式で表せない数の最大値を見つける。
bool app[1100000]; main(){ int t; cin>>t; while(t--){ memset(app,0,sizeof(app)); app[0]=true; rep(i,4){ int t; cin>>t; rep(i,1100000-t) if(app[i])app[i+t]=true; } int l1=0; rep(i,1000001)l1+=!app[i]; bool ok=true; for(int i=1000001;i<1100000;++i){ if(app[i]==0){ ok=false; break; } } cout<<l1<<endl; if(ok){ for(int i=1000000;;--i){ if(app[i]==0){ cout<<i<<endl; break; } } }else cout<<-1<<endl; } }