买不到的数目[蓝桥杯]

题目链接：买不到的数目
时间限制: 1 Sec 内存限制: 256 MB

题目描述：
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
输入保证两个正整数互质
输出：
一个正整数，表示最大不能买到的糖数

样例输入：
4 7
样例输出：
17

题意：找一个最大的不能组合出来的数字。
思路：几乎暴力，因为数据范围不大，那我们就逐个标记。

因为题中数据说两个数都不大于1000，那我们把数组p定义成1000000那么大，然后从头开始标记。

p[i]=1表示能组合出 i 这个数
p[i]=0表示不能组合出 i 这个数

我们假设两种包装数量分别是 a，b 假如一个数 i 可以被组合出来，那么 i+a ，i+b 是不是也可以被组合出来，就按这种思路从小到大标记，然后我们从大到小遍历，如果p[i]==0（我们是倒着遍历，所以第一个p[i]==0的数就是最大的不能被组合出来的数）那我们就输出就行了。

看代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000;
int p[maxn+1]={0};
int main()
{ int a,b; while(cin>>a>>b) { //cout<<a*b-a-b<<endl; memset(p,0,sizeof(p)); // 每次初始化一下 p[0]=1; for(int i=1;i<=maxn;i++) { if(i>=a&&p[i-a]) p[i]=1; else if(i>=b&&p[i-b]) p[i]=1; } for(int i=maxn;i>=1;i--) { if(!p[i]) { cout<<i<<endl; break; } } } return 0;
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

细心的的小可爱是不是看到了我那行注释的代码，那么恭喜你发现了这题的究极解法，没错就是只写那一条语句就行了。
至于这个解法就是数论了我就不多解释了，感兴趣的小可爱可以尝试证明一下。

究极代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{ int a,b; while(cin>>a>>b) { cout<<a*b-a-b<<endl; } return 0;
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

小可爱们看完别忘了点赞哟，谢谢支持！
如果你是电脑端，还可以看到右下角的 “一键三连” ，没错点它[哈哈]

加油！

共同努力！

Keafmd

文章来源: keafmd.blog.csdn.net，作者：牛哄哄的柯南，版权归原作者所有，如需转载，请联系作者。

原文链接：keafmd.blog.csdn.net/article/details/108855520