蓝桥杯2017年第八届真题-包子凑数(扩展欧几里得)

解题思路:
是否互质，然后完全背包
参考代码:

#include<bits/stdc++.h>
using namespace std;
#define maxx 400000
int all[maxx];
int ans,n;
int dp[maxx];
int main()
{
  cin>>n;
  for(int i=1;i<=n;++i) cin>>all[i];
  ans=all[1];
  for(int i=1;i<=n;++i)
  ans=__gcd(ans,all[i]);
  if(ans!=1) cout<<"INF";
  else 
  {
    dp[0]=1;
    for(int i=0;i<=maxx/4;++i)
     for(int j=1;j<=n;++j)
      dp[i+all[j]]=max(dp[i+all[j]],dp[i]);
     int ans1=0;
     for(int i=1;i<=maxx/4;++i)
     if(dp[i]==0) ++ans1;
     cout<<ans1;
  }
}