買不到的數(shù)目

小明開了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣。

小朋友來買糖的時候，他就用這兩種包裝來組合。當然有些糖果數(shù)目是無法組合出來的，比如要買 10 顆糖。

你可以用計算機測試一下，在這種包裝情況下，最大不能買到的數(shù)量是17。大于17的任何數(shù)字都可以用4和7組合出來。

本題的要求就是在已知兩個包裝的數(shù)量時，求最大不能組合出的數(shù)字。

輸入：

兩個正整數(shù)，表示每種包裝中糖的顆數(shù)(都不多于1000)

要求輸出：

一個正整數(shù)，表示最大不能買到的糖數(shù)

不需要考慮無解的情況

例如：
用戶輸入：
4 7
程序應該輸出：
17

再例如：
用戶輸入：
3 5
程序應該輸出：
7

資源約定：

峰值內(nèi)存消耗 < 64M
CPU消耗 < 3000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內(nèi)容。

所有代碼放在同一個源文件中，調(diào)試通過后，拷貝提交該源碼。

注意: main函數(shù)需要返回0
注意: 只使用ANSI C/ANSI C++ 標準，不要調(diào)用依賴于編譯環(huán)境或操作系統(tǒng)的特殊函數(shù)。
注意: 所有依賴的函數(shù)必須明確地在源文件中 #include ， 不能通過工程設置而省略常用頭文件。

提交時，注意選擇所期望的編譯器類型。

提示

ax+by=C,不定方程的解 a=4,b=7,C=17 這種情況下，xy實際上有解，72+（7-4）==37 -1*4
a,b互質(zhì)，一定有解且解的數(shù)目無窮
C是gcd(a,b)的倍數(shù)，方程一定有解，而且有無窮多解

條件：一定有解=》a,b互質(zhì)
條件2：xy都是大于等于0的整數(shù)，在這個限定條件下有的C是無解的，那么C的上界是多少呢？至多是a*b

代碼

#include <iostream> #include <set>using namespace std;int main(int argc, const char *argv[]) {int a, b;scanf("%d %d", &a, &b);set<int> ss; // 枚舉a*x+b*y的值，上邊界是a*bfor (int x = 0; a * x <= a * b; ++x)for (int y = 0; a * x + b * y <= a * b; ++y)ss.insert(ss.end(), a * x + b * y);for (int i = a * b; i >= 0; --i) {if (ss.find(i) == ss.end()){ //i不在set中，那么i就是答案printf("%d\n", i);return 0;}}return 0; }

升級版代碼

#include <iostream> using namespace std; int main (){int a,b;cin>>a>>b;cout<<a*b-a-b<<endl;return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的征战蓝桥 —— 2013年第四届 —— C/C++A组第8题——买不到的数目的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。