AcWing 1226. 包子凑数
原题链接
中等
作者:
最后五分钟
,
2024-03-28 20:33:58
,
所有人可见
,
阅读 5
#include<bits/stdc++.h>
#define LL long long
#define x first
#define y second
#define de(x) cout<<#x<<" = "<<x<<" "
#define deg(x) cout<<#x<<" = "<<x<<endl
using namespace std;
const int N=110,M=1e5;
typedef pair<int,int> PII;
int v[N];
int f[M];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int res=0,cd=v[1];
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>v[i];
cd=gcd(cd,v[i]);
}
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=v[i];j<1e5;j++)
{
f[j]=max(f[j],f[j-v[i]]);
}
for(int i=1;i<1e5;i++)
if(!f[i])res++;
if(cd==1)cout<<res<<endl;
else cout<<"INF"<<endl;
return 0;
}