包子凑数 蓝桥杯

关于这题的数学定理，如果 a,b 均是正整数且互质，那么由 ax+by，x≥0，y≥0 不能凑出的最大数是 ：a*b-a-b

想不起来的时候，把能列出来的数据列出来找规律，不互质得数不符合题目所说

类似于力扣零钱和分割等和子集

#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
  int i;
  while(i=x%y,i!=0){
    x=y;
    y=i;
  }
  return y;
}
int dp[9000000]={0},h=0;//能凑出来的数
int main()
{
 int n,i,j,g=1;
 cin>>n;
 int a[n+2];
 for(i=0;i<n;i++)
 cin>>a[i];
 g=gcd(a[0],a[1]);
 for(i=2;i<n;i++)
 g=gcd(g,a[i]);
 if(g!=1) {
   cout<<"INF";字符串这里是双引号
   return 0;
 }
 dp[0]=1;
 for(i=1;i<=900000;i++) 大概找出一个最大凑不出得数
 for(j=0;j<n;j++)
 {
   if(i>=a[j])
   dp[i]=dp[i]|dp[i-a[j]];有一个为真就为真
 }
 for(i=1;i<=900000;i++)
 {
   if(dp[i]==0)
   h++;
 }
 cout<<h;
 return 0;}