蓝桥杯包子凑数（完全背包、裴蜀定理）

悠悠 2021-07-17 02:57 433阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]  
思路：根据裴蜀定理，当所有种类的蒸笼包子数的最大公约数不为1时，凑不出的包子数为无限多，因为无论蒸笼怎么组合都必须得是gcd得倍数，gcd不为1一定会有凑不出的。如果能够凑的出的有限，那么到达某个界限后都是凑得出的，这个界限为Ai\*Ai=10000，或许会有人问为啥是这个数，这个具体证明我也搞不出，但可以模拟一下你取任意两个互质的数，如6，7，会发现42之后任意一个数都是可以通过6，7组合出来，姑且就当个结论记了八。然后就是对凑不出的数的一个求解，这个可以通过完全背包解决。

dp\[i\] 表示凑出i个包子的方法总数，简单说就是如果其>=1就凑得出，==0就凑不出。

状态转移方程： dp\[i\]=dp\[i-第j种蒸笼包子数\]+1 (dp\[i-第j种蒸笼包子数\]>=1) 当i-第j种蒸笼包子数是可以凑成的，那么我只需对其+第j种蒸笼包子数就可以凑成i个包子数。

Code:

#include<iostream>
    #include<map>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<string>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    
    ll dp[10005];
    
    int lst[Max];
    
    int gcd(int a, int b)
    { 
    	if (a == 0)return b;
    	return gcd(b % a, a);
    }
    
    int main()
    { 
    	int n;cin >> n;
    	for (int i = 1;i <= n;i++)cin >> lst[i];
    
    	int g = lst[1];
    	for (int i = 2;i <= n;i++) g = gcd(g, lst[i]);
    
    	if (g != 1)cout << "INF" << endl;
    	else
    	{ 
    		dp[0] = 1;
    		for (int i = 1;i <= n;i++)
    		{ 
    			for (int j = 1;j <= 10004;j++)
    			{ 
    				if (j - lst[i] >= 0 && dp[j - lst[i]] >= 1)dp[j]++;
    			}
    		}
    		int ans = 0;
    		for (int i = 1;i <= 10004;i++)
    		{ 
    			if (dp[i] == 0)ans++;
    		}
    		cout << ans;
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FzYmJ2_size_16_color_FFFFFF_t_70]: /images/20210716/ed6c794d0831429fbff2031529ac3b35.png