历届试题买不到的数目

问题描述

小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入格式

两个正整数，表示每种包装中糖的颗数(都不多于1000)

输出格式

一个正整数，表示最大不能买到的糖数

样例输入1

4 7

样例输出1

样例输入2

3 5

样例输出2

思路：

首先定义一个上限，上限的值取为两个数的最小公倍数初始化（默认初始化为0）

对数组的元素开始往前处理
遇到的第一个值不能表示的元素输出，而一个数能不能表示直接枚举就行，从后向前只是更快找到答案

代码一

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int test(int m,int n,int num)
 4 {
 5     int s=0;
 6      for(int i=0;i<=n;i++)
 7     {
 8         for(int j=0;j<=m;j++){
 9                 if(num==(m*i+n*j)){
10                     s=1;
11                 }
12         }
13         if(s==1) break;
14     }
15     return s;
16 }
17 int gcd(int m,int n)
18 {
19     int a=1;
20     int i=2;
21     while(true){
22             if(i>=min(m,n)){
23                 break;
24             }
25         if(m%i==0 && n%i==0){
26             m/=i;
27             n/=i;
28             a*=i;
29             continue;
30         }
31         else{
32             i++;
33         }
34 
35     }
36     return a*m*n;
37 }
38 int main()
39 {
40     int m;
41     int n;
42     cin >> m >> n;
43     int s=gcd(m,n);
44     int Big=1;
45     for(int i=s-1;i>=1;i--)
46     {
47         if(test(m,n,i)==0) {
48             Big=i;
49             break;
50         }
51     }
52    cout << Big << endl;
53     return 0;
54 }

为啥上限是最小公倍数？

一种比较好理解的思路是：以29为例，如果28可以，那么29一定可以。因为2个4减去一个7等于1。也就是用两个4替换一个7。30也一定可以，因为可以用2个7替换3个4，以此类推。无论此时的数与最小公倍数m差多少，一定可以通过把i个4换成j个7的形式得到。

下面是网上的一个答案

代码二

 1 #include<iostream>  
 2 
 3   
 4 
 5 using namespace std;  
 6 
 7   
 8 
 9 int main()  
10 
11 {  
12 
13       
14 
15     int a,b;  
16 
17     cin>>a>>b;  
18 
19     cout<<a*b-a-b<<endl;  
20 
21       
22 
23 }

这种是直接用了定理（扩展欧几里得）、

自然数a,b互质,则不能表示成ax+by（x,y为非负整数）的最大整数是ab-a-b.
证明：
a或者b是1的情况下容易证明.
以下情况都是a>1且b>1的情况.
首先证明ab-a-b不能表示成ax+by
假设ab-a-b=ax+by,那么ab=am+bn (m,n都大于等于1)
左边是a的倍数,右边am是a的倍数,那么要求bn也要是a的倍数
b不是a的倍数,只能要求n是a的倍数,这样的话,bn=bn’a>=ba
那么am=ab-bn<=0就与am>1矛盾.

历届试题 买不到的数目

历届试题买不到的数目