---
title: "包子凑数（未解决）"
created: 2025-11-28
tags:
  - 算法
---

# 包子凑数（未解决）

## 题目 [包子凑数](https://www.acwing.com/problem/content/description/1228/)

![[image-213562ba.png]]

## 思路分析

乍一看感觉和前面的那个砝码称重差不多 也是用count或bool作属性看选出的数量

但是这里问的是选不出的数量 一开始理所当然的直接把总的减去选的出的就是选不出的

但发现并不是这么简单

题目说会出现有无限个数被凑不出来的， 说明这些数的gcd不是1

这里用到裴蜀定理 ，任意两个数的组合必定是他们gcd的的倍数，同样可以推广到更多数：

如果这些数的gcd是d，那么他们的组合是d的倍数，如果d不是1，那么必然有无限个数无法被组合出来。

所以，要先写个欧几里得算法，两两求下gcd，看gcd是否大于1。

欧几里得算法：gcd(a,b)=gcd(b,a%b)。当余数为0时，当前算式的除数就是a和b的gcd。 那么，gcd为1呢？最大不能表示出来的数必定有个上界，因为两个数a,b（当gcd=1时），最大不能表示出来的数是：(a−1)(b−1)−1
当数字更多的时候，这个上界必然更小（可选的数字变多了），而99和98是100内最大的互质的数，所以这个上界选择10000

那么下面的事情就是看这么多数中有多少个不能被组合出来，回到了刚开始分析的完全背包问题

大概就是 要先计算一下公因数 公因数不是1的话就一定有INF个求不出来

把这个情况解决了 然后就是前面那种用count或bool的完全背包求方案数问题

emmm 放弃这题了

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=10010;

int n,m;

int w[110];

int f[110][N];

int gcd(int a,int b){

    return b?gcd(b,a%b):a;

}

int main()

{

    cin>>n;

    int d=0;

    for(int i=1;i<=n;i++){

        cin>>w[i];

        d=gcd(d,w[i]);

    }

    if(d!=1)

        cout<<"INF";

    else{

        for(int i=0;i<=n;i++)

            f[i][0]=1;

        for(int i=1;i<=n;i++){

            for(int j=0;j<N;j++){

                f[i][j]=f[i-1][j];

                if(j>=w[i])

                    f[i][j]+=f[i][j-w[i]];

            }

        }

        int cnt=0;

        for(int j=1;j<N;j++){

            if(!f[n][j])

                cnt++;

        }

        cout<<cnt;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[混合背包问题|混合背包问题]] 🏠 [[00-刷题理模型]] ➡️ [[砝码称重|砝码称重]]