自动搬运

查看原文

来自洛谷，原作者为

	0x282e202e2029 I love U Bones

搬运于2025-08-24 22:41:02，当前版本为作者最后更新于2023-04-26 19:14:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解

为了红名疯狂写题解的蒟蒻又来啦~

题目传送门

前置知识

​在数论中，裴蜀定理是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数 $a$、$b$ 和它们的最大公约数 $d = \gcd(a, b)$，关于未知数 $x$ 和 $y$ 的线性丢番图方程

有解当且仅当 $d | m$。裴蜀等式有解时必然有无穷多个整数解。

特别来说，方程 $ax + by = 1$ 有解当且仅当整数 $a$ 和 $b$ 互素。

对于多个整数而言，情况是类似的。

思路

为方便，这里我们使用 $\gcd(\{A_i\})$ 表示 $\{A_i\}$ 中所有数的最大公约数。

首先，一个显而易见的结论是：

当 $\gcd(\{A_i\}) = 1$ 时，凑不出的数目只有有限多个；而当 $\gcd(\{A_i\}) > 1$ 时，凑不出的数目有无限多个。

看到大佬们似乎都对这个结论一笔带过，这里蒟蒻就给出证明方式：

首先，由裴蜀定理可得，当 $\gcd(\{A_i\}) = 1$ 时，对于任意 $X \in \mathbb{N^+}$，方程

都存在无穷多个整数解，那么必定只有有限多个 $X$，使得该方程无自然数解。

证毕。

判断出是否输出 INF 后，我们就可以使用 dp 的做法将剩余情况处理掉了。

dp 数组只用开 $100005$ 的大小，对于本题的数据范围足够了。

注意到如果某个 $k - A_i$ 能被凑出，$k$ 也必能被凑出，因此状态转移方程为 $dp_k = \max(dp_k,dp_{k - A_i})$（注意写法！一定是 $\max$！否则有可能原本可以的数变得不行了，然后全 WA）。

AC 代码

#include <bits/stdc++.h>
using namespace std;
int gcd(int m, int n)
{
	if(n)
	{
		return gcd(n, m % n);
	}
	else
	{
		return m;
	}
}//求gcd(m,n),常见的递归写法
const int MAXN = 105, MAX_DP = 100005;//又来定义
int n, a[MAXN], dp[MAX_DP], ans;
bool notCoprime(int *arr)//返回arr数组中所有数的最大公约数是否大于1
{
	int g = arr[0];
	for(int i = 1; i < n; i++)
	{
		g = gcd(g, arr[i]);
		if(g == 1)
		{
			return false;//如果g已经为1，不用再循环，直接返回
		}
	}
	return g > 1;
}//定义函数，运行更快
int main()
{
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}//输入
	if(notCoprime(a))//如果gcd({A_i})>1
	{
		printf("INF");
		return 0;//直接结束
	}
	dp[0] = 1;//注意0是被认为能被凑出的，否则所有数都凑不出来，循环检查时可以不用从0开始
	for(int i = 0; i < n; i++)
	{
		for(int j = a[i]; j < MAX_DP; j++)
		{
			dp[j] = max(dp[j], dp[j - a[i]]);//状态转移方程
		}
	}
	for(int i = 1; i < MAX_DP; i++)
	{
		if(!dp[i])
		{
			ans++;//如果dp[i]=0,多一个凑不出的数
		}
	}
	printf("%d", ans);//输出
	return 0;
}

AC 记录