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;
  }
}