您当前的位置: 首页 >  蓝桥杯

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

2017年蓝桥杯B组C/C++省赛-包子凑数

不牌不改 发布时间:2022-03-15 10:19:36 ,浏览量:0

题目

题目链接

题解

数论、动态规划。

数论知识:如果 a a a 和 b b b 互质,则 x ∗ a + y ∗ b x*a+y*b x∗a+y∗b 无法得到的最小值为 a ∗ b − a − b a*b-a-b a∗b−a−b,又即 ( a − 1 ) ∗ ( b − 1 ) (a-1)*(b-1) (a−1)∗(b−1)。

比如 2 2 2 和 3 3 3,不可以构成 1 1 1,可以构成 2 2 2,可以构成 3 3 3,可以构成 4 = 2 + 2 4=2+2 4=2+2,可以构成 5 = 2 + 3 5=2+3 5=2+3,……,之后的数都可以构成。 1 1 1 是无法由 2 2 2 和 3 3 3 构成的最大整数,即 2 ∗ 3 − 2 − 3 = 1 2*3-2-3=1 2∗3−2−3=1。

如果 a a a 和 b b b 不是互质的话,很显然无法构成的数是无穷多个的。

比如 2 2 2 和 4 4 4,只能构成 2 2 2 的整数倍,也就是偶数,对于奇数是构造不出来的。

对于每笼包子可以选任意多次,联想到完全背包。

对应到本题上,如果这些数无法构成的数不是无穷多个,那么我们就可以用完全背包判断一定范围内的数是否可以由前面的数凑数来,只要范围足够大就行了,最后统计无法凑出来的数的数量;如果这些数无法构成的数有无穷多个,那么需要特判一些情况:

  1. 当笼数为 1 1 1时。只有一笼包子,那么只有这笼中包子的数目为 1 1 1时,才能保证不是无穷,其他数目均无穷;
  2. 当笼数非 1 1 1时。至少存在两个数是互质才能保证构造出来的数不是无穷多个。判断若干个数是否存在互质的数,只要判断它们的最大公因子是否为 1 1 1,如果为 1 1 1,说明存在两个数互质,否则说明它们都是一个数的倍数,那么也就只能构成该最大公因子的倍数,所以无法构成的就是无穷多个。
代码
#include
using namespace std;

const int N = 1e4+10;

int dp[N+10], n, a[110], ans;

int main()
{
	cin >> n;
	for (int i = 1;i > a[i];
	
	if (n == 1) { // 一笼包子,只有这笼包子个数为1才能保证不存在无穷个数无法组成 // 这个判断可有可无有,测试数据没有 
		if (a[1] != 1) cout             
关注
打赏
1662186765
查看更多评论
0.0419s