題目描述

小明開(kāi)了一家糖果店。他別出心裁：把水果糖包成4顆一包和7顆一包的兩種。糖果不能拆包賣(mài)。
小朋友來(lái)買(mǎi)糖的時(shí)候，他就用這兩種包裝來(lái)組合。當(dāng)然有些糖果數(shù)目是無(wú)法組合出來(lái)的，比如要買(mǎi) 10 顆糖。
你可以用計(jì)算機(jī)測(cè)試一下，在這種包裝情況下，最大不能買(mǎi)到的數(shù)量是17。大于17的任何數(shù)字都可以用4和7組合出來(lái)。
本題的要求就是在已知兩個(gè)包裝的數(shù)量時(shí)，求最大不能組合出的數(shù)字。

輸入

兩個(gè)正整數(shù)，表示每種包裝中糖的顆數(shù)(都不多于1000)
輸入保證兩個(gè)正整數(shù)互質(zhì)

輸出

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

樣例輸入

4 7

樣例輸出

17

解法一:
代碼如下：

#include <iostream> using namespace std;int main() {int p,q;cin>>p>>q;cout<<p*q-p-q<<endl;return 0; }

結(jié)論：
如果a,b均是正整數(shù)且互質(zhì)，那么由ax+by，x>=0,y>=0,不能湊出的最大數(shù)是a*b-a-b

解法二:

#include <iostream> using namespace std; const int N = 1000010; int vis[N];int main() {int a, b;int ans;cin >> a >> b;vis[a] = 1;vis[b] = 1;for (int i = 0; i <= a * b; i++) {if (vis[i] == 1) {vis[i + a] = 1;vis[i + b] = 1;}}for (int i = 0; i <= a * b; i++) {if (vis[i] == 0)ans = i;}cout << ans << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的蓝桥杯第四届初赛-买不到的数目-数论的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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