试题历届试题买不到的数目（dp/数学）

墨蓝 2023-07-18 14:11 49阅读 0赞

# 试题 历届试题 买不到的数目 #

--------------------

资源限制
    时间限制：1.0s   内存限制：256.0MB

$Daily English

> 曾几何时，我流连梦境，心比天高，人生充满希望。  
> I dreamed a dream in time gone by,when hope was high and life worth living.

## 问题描述 ##

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

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

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

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

## 输入格式 ##

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

## 输出格式 ##

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

样例输入1

4 7

样例输出1

样例输入2

3 5

样例输出2

## 思路 ##

本题蕴含了：a与b一定是互质的，而且a，b均大于1。  
为什么？  
(都怪出题人没有说清楚)  
认真看题目这段描述：  
把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。  
小朋友来买糖的时候，他就用这两种包装来组合。

**结合生活实际**，如果a = 4,b = 8,那这个b **对商家而言**有什么意义？  
小朋友完全可以买两个a代替一个b。  
如果a,b中有一个为1，那就一定求不到正整数结果,因为1可以组合出任意的正整数（废话）。.

way1 dp：

令dp\[i\]表示i是否可以由a,b组合得到，  
dp\[i\] = 1 表示可以，dp\[i\] = 0则表示不可以。  
那么对于一个数i,有三种情况：

1.  i本身就是a,b中得一个;
2.  i 可以由 i - a 加上一个a或b得到;
3.  i 可以由 i - b 加上一个a或b得到;

所以就有状态转移方程：  
假设a < b,  
i = a 或 i = b 时：dp\[i\] = 1；  
i < b 时: dp\[i\] = dp\[i-a\] ；  
i > b 时: dp\[i\] = dp\[i-a\] || dp\[i-b\]；

有了递推方程，还需要**确定i的上限**。  
我们刷题，完全可以把i的上限 根据时间复杂度 设置为一个比较大的值，但是不超过时间复杂度。  
因为可以在O(N)的时间复杂度了求解答案，且题目给出a,b不会超过1000，  
所以我们可以 （再结合做题经验 ）把i的上限设置为1e6，或者2e6,5e6等等。。

但是AC完，我们还是需要认真思考一下：i的上限应该为多少？该如何来证明它的上限值？

我思考了很久，没有很好的思路…只知道上限在a \* b范围内。but我无法证明，表示很无奈。。。（暂时留坑）

--------------------

way2 数学解法：  
a,b互质，则a,b最大不能组合出的正整数：ans = a \* b - a - b。

我能力有限，暂时无法直接证明：ans = a \* b - a - b。

不过看了别人使用反证法证明了a \* b - a - b 一定是不能由a,b组合得到的。

我把**反证法**证明表述如下：

假设：a\*b-a-b 可以由a,b组合得到，则: a \* b - a - b = a \* x + b \* y ,(x>=0,y>=0)

a \* b = a \* (x + 1) + b\* (y + 1)， x+1>=1,y+1>=1

可知: a \* b > b \* (y + 1), b \* (y + 1) 一定是a的倍数

又因为： gcd(a,b) = 1,所以：b不可能为a的倍数

所以只能是y + 1 为a的倍数，即: y + 1 = k \* a ,(k > 0)

但是这就使：a \* b > b \* (y + 1) = k \* a \* b 产生了矛盾，

所以假设不成立，即 a \* b - a - b 不可以由a,b组合得到。

此时 只要证明a,b不能组合出的 最大正整数 < a \* b ，

那么就可以说明：

a \* b - a - b 就是题目ans了。

## 代码 ##

way1 dp:

#include <iostream>
    using namespace std;
    const int N = 1e6;
    int dp[N];
    int main()
    {
        
        int a,b;
        cin>>a>>b;
        dp[a] = dp[b] = 1;
        int up = a * b;//题意以及结合生活实际：a,b一定互质
        if(b < a) a ^= b ^= a ^= b; //交换a,b,保证更小的是a
        int ans = a - 1;
        for(int i = a+1; i < up; i++)
        {
        
            if(i == b) continue;
            if(i > b)
                dp[i] = dp[i-a] || dp[i-b]; //可能+a得到i，或者+b得到i
            else
                dp[i] = dp[i-a]; //只可能+a得到i
            if(dp[i]) continue;
            ans = i;
        }
        cout<<ans<<endl;
        return 0;
    }

way2：  
code:

a,b = map(int,input().split())
    print(a*b-a-b)