lanqiao OJ 98 包子凑数

#include<iostream>
#include<cstring>
#include<algorithm>
 
using namespace std ;
 
const int N = 1e6 ;
bool f[N] ;
int a[N] ;
int main(){
  int n ; cin >> n ;
  int g ;
  for(int i = 1 ; i <= n ; i++){
    cin >> a[i] ;
    if(i==1) g = a[i] ;
    else g = __gcd(g,a[i]) ;//记录所有包子数的一块的质数 ， 如果所有数都互质，那就一定能凑出大部分数 
  }
  f[0] = 1 ;
  for(int i = 1 ;i <= n ;i ++){
    for(int j = 0 ;j <= 1e6 ; j ++ ){
      if(j >= a[i]) if(f[j-a[i]]) f[j] = 1 ;//递推合法状态 
    }
  }
  if(g!=1){
    cout << "INF" << endl ;
  }else {
    int ans = 0 ;
    for(int i = 0; i <= 1e6 ; i ++) if(!f[i])ans ++ ;
    cout << ans << endl ;
  }
 
}