提示信息：
因数：因数是指整数a除以整数b(b≠0)的商正好是整数而没有余数，我们就说b是a的因数。
公因数：给定若干个整数，如果有一个(些)数是它们共同的因数，那么这个(些)数就叫做它们的公因数。
互质数：公因数只有1的两个非零自然数，叫做互质数；例如2和3，公因数只有1，为互质数。
题目描述：
某商店将一种糖果按照数量打包N和M两种规格来售卖(N和M为互质数，且N和M有无数包)。这样的售卖方式会限制一些数量的糖果不能买到。那么在给出N和M的值的情况下，请你计算出最多不能买到的糖果的数量.
例如：当N=3,M=5,3和5为互质数，不能买到的糖果数量有1，2，4，7，最多不能买到的糖果数量就是7，7之后的任何数量的糖果都是可以组合购买到的。
输入描述：输入两个正整数N，M(2<N<M<100，N和M为互质数)，表示两种规格的糖果数量，正整数之间一个空格隔开。
输出描述：输出一个整数，表示最多不能买到的糖果数量
样例输入：3 5
样例输出：7
读完整个题目之后，大家心里或许会有一个疑问：难道从某个数之后，所有的数字都能被组合出来吗？是的！这道题如果你知道一个公式就很简单了：最大不能组合出来的数字为=
a*b-a-b(前提是a、b是互质的两个数)，这个公式后面会给予证明，如果你不能理解证明的过程，记住结论即可，这属于数论上的知识。
这道题的做法有好几种，可以通过暴力枚举，可以通过公式，可以通过动态规划。我们逐一进行讲解，注意：在讲解的过程中，如果有任何不明白的地方，可以给up主留言。
方法一：暴力枚举方法解题
分析：在不知道公式的情况下，就只能用暴力枚举的方法了，首先要知道的就是枚举范围了，那这个枚举范围怎么确定呢？如果你看不出来的话，就猜吧，虽然这样特别扯，但是总比不做好，这个不能组合的数范围肯定不会特别大，最好猜的就是ab了，把ab内所有可能的解枚举出来，然后从后往前找不能被组合出来的数，那么第一个找到的数就是最大不能组合数
猜我们要怎么猜呢，我们可以举特殊例子，不妨假设N=3，M=5，这里的N和M代表两种糖果的规格数量，可以列一个表格：
猜出了要枚举的范围是N*M以内，那怎么去写代码呢？核心代码如下：
（1）从a*b开始从后往前枚举：
for(int k = N * M; k>= 1; k--)（2）如果说能够使得Ni+Mj=k等式不成立，那么k就是我们要找的不能组合的数，其中N和M表示两种糖果的规格数量，i和j是自然数，表示N包装和M包装的包数，要注意i和j的取值是可以为0的，因为可以买0包，比如15这个数，我们可以买0包包装为3个数量的和3包包装为5个数量的或者5包包装为3个数量的和0包包装为5个数量的。
（3）接下来我们就需要来确定i和j的枚举范围了，按照题目的意思N和M的范围处在2到100之间，因为要枚举的数是从N*M开始，也就是说k的范围最大为100*100=10000，我们不妨取i的最大值为100，为什么呢？我们取极端的情况，假设N和M的值都为100，既然k的最大范围为N*M=100*100=10000，那么当i的值=100的时候，k的最大值就能取到，所以i的最大范围取100即可。那么i确定以后，j的值可以不用枚举，直接通过k和i计算出来,只要i在0-100之间的某个取值能够使得等式成立，那么k就是能够被组合出来。比如：当N=3，M=5，i=3，K=14，那么根据公式Ni+Mj=k，可以推出当k=20，3*3+5*j=14，那么5*j=14-9，此时j=1，那么当i=3，j=1时，k=14，因此14能够被组合出来。注意：到底k能不能被组合出来一定要看当i等于0-100之间的每种数量的情况，当且仅当当i取0-100之间的任何一个数都不能使等式成立的情况下，k就是我们要找的数。为什么我这里只提了i呢？因为当i确定之后,j的值是可以计算出来的。
代码如下：
#include<bits/stdc++.h> using namespace std; int N,M; int main() { cin >> N >> M; for(int k=N*M;k>=1;k--) { int flag=0; for(int i=0;i<100;i++) { int q=k-N*i; if(q>=0&&q%M==0) { flag=1; break; } } if(flag==0){ cout<<k<<endl; break; } } return 0; }我们来解释一下代码：刚刚我们已经解释了k要从N*M开始从后往前枚举，在枚举的过程中，我们确定i的范围为0到100，请注意：在代码里面的q代表的含义是需要被组合出来的数，而不是糖果的包数，而i代表的就是糖果的包数。
以下代码代表要开始从N*M开始进行枚举：
for(int k=N*M;k>=1;k--) { }在for循环的内部，我们需要去确定当i取得0-100的某个值时，是否会使得等式Ni+Mj=k成立，如果成立，说明k是可以被组合出来的，否则k就是我们要找的最大组合的数。此时这里的q代表的就是Mj整体，需要判断q是否为M的倍数，且需要判断q的值是否大于等于0，为什么呢？因为q的值如果小于0，也可能会使等式成立，比如当N=3,M=5，通过计算，我们得出3，5最大不能被组合出来的数字为7，假设k=7，i=4，那么q=7-12=-5，如果没有q>=0这个条件，只有q%M==0这个条件，那么if条件就会成立，说明7能够被组合出来，但其实q已经是负数了，7是无法被组合出来的，所以要排除负数的情况。
暴力枚举代码的写法有很多种，上面是其中一种，当然，这里可以提供给大家另一种写法，
利用c++的STL之set来编写代码：
#include<bits/stdc++.h> using namespace std; int main() { set<int> s; int a,b; cin>>a>>b; for(int x=0;a*x<=a*b;x++) //枚举a*b以内的所有解 { for(int y=0;a*x+b*y<=a*b;y++) { s.insert(a*x+b*y); //0 5 10 15 3 8 13 6 11 9 14 12 ==> 7 4 2 1 } } for(int i=a*b;i>=0;i--) { if(s.find(i)==s.end()){ cout<<i<<endl; break; } } return 0; }
方法二：公式法解题
分析：这道题如果你会：最大不能组合的数=N*M-N-M，那么这道题就非常简单了。不仅简单，还能保证不超时。有的小伙伴可能不满足于只懂得怎么算，还想要知道为什么这样算？这个公式是怎么推理出来的？现在就给大家讲一讲，如果你觉得很难，看不下去，那么可以跳过，只需背诵这个公式即可，不用有太大的压力。
题意：去掉题目背景，我们可以把问题抽象为：有两个正整数a、b。可以组成任意线性组合ax+by，x,y非负，求最大不能组合的数。
如果两个正整数有最大不能组合出来的数，那么这两个数一定互质，这是大前提。
为什么呢？是可以证明的：
确保a,b两数互质之后 ，就可以开始来推算这个公式了，当然，这个公式的推算是需要一定数学基础的，如果你没有，可以不看，对你做题也没有影响。
证明出公式之后，那么这道题就很好做了
#include<bits/stdc++.h> using namespace std; int main(){ int a,b; cin>>a>>b; cout<<a*b-a-b<<endl; return 0; }总结：还是那句话，证明过程如果看不懂没关系，记住公式就可以了！毕竟应用最重要。
方法三：动态规划解题
我们可以定义一个状态数组，比如 int a[100005]，a[i]=1代表i这个数能够被组合出来，a[i]=0代表i这个数不能被组合出来。一开始将a[0]=1初始化为1，因为0这个数肯定是能被组合出来的。然后遍历1-N*M范围内的所有数，将能够组合出来的数i对应的a[i]标记为1,最后从后往前筛选，找出最大的不能被组合出来的数字。
#include<bits/stdc++.h> using namespace std; int a[100005]; int main() { int t=0,N,M; cin>>N>>M; a[0]=1; for(int i=1;i<=N*M;i++) //i能否被组合出来 { if(i>=N&&a[i-N]) //所有小于n和小于m的数据都不能被组合出来 { a[i]=1; // a[3]=1 a[6]=1 a[8]=1 a[9]=1 a[11]=1 a[12]=1 a[13]=1 a[14]=1 a[15]=1 } else if(i>=M&&a[i-M]){ // a[5]=1 a[10]=1 a[i]=1; } } for(int i=N*M;i>=0;i--) { if(!a[i]){ cout<<i<<endl; break; } } return 0; }分析：能被标记成1的就相当于是能被组合出来的数，起始让a[0]为1，这样在循环的时候就可以先把n和m标记成1，这两个数也确实是可被m、n线性组合出来的（让另一个系数为0）；如果一个数i被标记成1，那么i+n、i+m也可以被组合出来，所以也标记上1。循环的边界同样是m*n。
另一种代码写法：
#include <cstdio> #define mx 1000005 int data[mx]; int main(){ int i, j, a, b; scanf("%d%d", &a, &b); printf("%d %d\n",a,b); data[a] = data[b] = 1; //i从哪里开始比较好？不能从a+b开始，比如4+7 那就从11开始了 8就被略过了，从最小的那个开始 for (i =(a<b?a:b); i <= a*b; ++i){ if ((i-a)>=0&&data[i - a]) ++data[i]; //13 3 if ((i-b)>=0&&data[i - b]) ++data[i]; //3 13 } for (i = a*b;i>=0; --i) { if(data[i]==0) { printf("%d", i); break; } } return 0; }还有一种写法，也是动态规划的写法，比前面两种更标准一点，令dp[i] = 1表示i能够由n和m组成，否则不能，则有dp[i] = dp[i-n]||dp[i-m] ? 1 : 0;
#include<bits/stdc++.h> using namespace std; const int maxn = 1000005; int dp[maxn]; int main() { int n, m; while(scanf("%d%d", &n, &m) != EOF) { memset(dp, 0, sizeof(dp)); dp[n] = 1, dp[m] = 1; int t = min(n, m); //4 13 for(int i = t ; i < maxn; i++) { if((i-n)>=0&&dp[i - n] || (i-m)>=0&&dp[i - m]) dp[i] = 1; } for(int i = maxn - 1; i >= 0; i--) { if(!dp[i]) { printf("%d\n", i); break; } } } return 0; }
总结：以上讲解了几种最大不能组合数的求解方法，如果你觉得有疑问，可以添加up主的微信咨询，如果想学习相关算法，可以添加up主微信邀请入群，如下：
文章来源地址https://www.toymoban.com/news/detail-407886.html文章来源：https://www.toymoban.com/news/detail-407886.html
到了这里，关于买不到的数目(最大不能组合的数)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
