試題 歷屆試題 買不到的數目

---

資源限制 時間限制：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

17

樣例輸入2

3 5

樣例輸出2

7

思路

本題蘊含了：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,有三種情況：

i本身就是a,b中得一個;

i 可以由 i - a 加上一個a或b得到;

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,保證更小的是aint 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得到ielsedp[i] = dp[i-a]; //只可能+a得到iif(dp[i]) continue;ans = i;}cout<<ans<<endl;return 0; }

way2：
code:

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

總結

以上是生活随笔為你收集整理的试题 历届试题 买不到的数目（dp/数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。