题目链接
题解数论、动态规划。
数论知识:如果 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 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
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?