数论+完全背包

1.如何确定有解无解。

若这n个数是互质的，即最大公约数d=1，则说明一定有有限个数凑不出来，即有解。

若n个数并不是互质的，即最大公约数>1，则说明有无限个数凑不出来，即无解。

具体看y总证明。

2.有解的情况求解

对于n个数来说，若有解，最大不能凑出的数是N = (100 - 1) * (99 - 1) - 1，这样能够确定我们背包问题的最大体积。

最终扫描一遍凑不出的体积数量即为答案。

$ 时间复杂度O(NM)，空间O(M)$

每个状态只和上层状态有关，因此可以状态压缩到一维

参考文献

蓝桥杯辅导课

AC代码

#include <iostream>
using namespace std;

const int N = 1e5 + 10;

int n, d;
bool f[N];
int w[N];

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 >> w[i];
        d = gcd(d, w[i]);//最大公约数
    }

    //分情况讨论是否有解
    if (d > 1) cout << "INF\n";
    else {
        //有解

        f[0] = true;//初始化
        //背包DP
        for (int i = 1 ; i <= n ; i ++){
            for (int j = w[i] ; j < N ; j ++){
                f[j] |= f[j - w[i]];
            }
        }

        //统计不可凑出的数
        int res = 0;
        for (int i = 0 ; i < N ; i ++) 
            if (!f[i])
                res ++;

        cout << res;
    }


    return 0;
}