包子凑数_(完全背包，数论)

原题链接：1226. 包子凑数 - AcWing题库

题意：给定一些数，问这些数不能组成的数的数量有多少，每个数无限次数选择

思路

是完全背包

但是如何确定问题的遍历规模？ 也就是 j 要遍历到多大才可以，实在不行就往大的开

数论

实际上是数论问题，当给定一些整数时，其组合数是这些数最小公约数的倍数

只有最小公约数是1时才可能可以表示所有的数，如果不是，则一定有无限个数不能表示

那在确定的互质正整数的组合中，最大的不能被表示的数是多大呢？ 结论：$(a-1)(b-1)-1$

裴蜀定理_百度百科 (baidu.com)

在本题中，上限一百，最大的互质数是 99 和 100，即最大范围不超过 $1e5$

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 1e5 + 10;
 
int n;
int a[N];
bool f[N];
 
 
int gcd(int a, int b)
{
    if(!b) return a; 
    return gcd(b, a % b);
}
 
 
 
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++)
    {
        cin >> a[i];
        f[a[i]] = true;
    }
    
    int g = 0;
    for(int i = 0; i < n; i ++)
    {
        g = gcd(g, a[i]);
    }
    
    if(g != 1)
    {
        //cout << g << endl;
        puts("INF");
        return 0;
    }
    
    for(int i = 0; i < n; i ++)
        for(int j = 1; j < N; j ++)
            f[j] = f[j] | f[j-a[i]];
    
    int cnt = 0;
    for(int i = 1; i < N; i ++)
        cnt += !f[i];
        
    cout << cnt << endl;
    
    return 0;
}