1226. 包子凑数 - AcWing题库
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n , d = 0;
int a[N];
bool dp[N][10005];
int gcd(int a,int b)
{
return b ? gcd(b , a % b) : a;
}
int main()
{
cin >> n;
for(int i = 1 ;i <= n;i ++)
{
cin >> a[i];
d = gcd(d , a[i]);
}
memset(dp , 0 , sizeof dp);
dp[0][0] = true;
if(d != 1) cout << "INF";
else{
for(int i = 1;i <= n;i ++)
{
for(int j = 0;j <= 10000;j ++)
{
dp[i][j] = dp[i - 1][j] || (j >= a[i] ? dp[i][j - a[i]] : false);
}
}
int ans = 0;
for(int j = 0;j <= 10000 ; j ++)
if(!dp[n][j]) ans ++;
cout << ans;
}
return 0;
}