题目描述
小明开了一家糖果店。
他别出心裁:把水果糖包成4颗一包和7颗一包的两种。
糖果不能拆包卖。
小朋友来买糖的时候,他就用这两种包装来组合。
当然有些糖果数目是无法组合出来的,比如要买 10 颗糖。
你可以用计算机测试一下,在这种包装情况下,最大不能买到的数量是17。
大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时,求最大不能组合出的数字。
输入格式
两个正整数 n,m
,表示每种包装中糖的颗数。
输出格式
一个正整数,表示最大不能买到的糖数。
数据范围
2≤n,m≤1000
,
保证数据一定有解。
样例
输入样例
4 7
输出样例:
17
暴力搜索猜公式
根据斐蜀定理可得,两个互质的数字x, y一定存在常数a, b使得:
ax + by = 1(gcd(x, y) == 1)
此时我们希望ax + by凑出的目标数大一些,假设为s:
asx + bsy = s
在等式左边加减xy得:
asx - xy + bsy + xy = s
整理如下:
x(as - y) + y(bs - x) = s
此时我们发现一种暴力搜索的做法:
先保证一个数字不变,改变另一个看是否可以凑出目标数字s。
#include<iostream>
using namespace std;
int n, m;
bool dfs(int s, int x, int y){
if (!s)return true;//当s = 0时,说明是可以凑出来的
if (s >= x && dfs(s - x, x, y))return true;
if (s >= y && dfs(s - y, x, y))return true;
return false;
}
int main(){
cin >> n >> m;
int res = 0;
for (int i = 1; i <= 100; i++){
if (!dfs(i, n, m))res = i;
}
cout << res << endl;
return 0;
}
我们经过查找对结果进行整理得:
| x y s | x y s |
| 3 5 7 | 3 7 11 |
| 4 5 11 | 4 7 17 |
| 6 5 19 | 5 7 23 |
| 7 5 23 | 6 7 29 |
| 8 5 27 | 8 7 41 |
| 9 5 31 | 9 7 47 |
横向对比y:每次y+k,s都会对应+k(x - 1)
纵向对比x:每次x+k,s都会对应+k(y - 1)
我们可以总结出如下规律:
1.y + 1 –> s + (x - 1)
2.x + 1 –> s + (y - 1)
将变化整合为公式即为:
s = (x - 1)(y - 1)
最终使用公式得代码如下:
#include<iostream>
using namespace std;
int n, m;
int main(){
cin >> n >> m;
cout << n * m - n - m << endl;
return 0;
}
最后还有个 + 1忘记写了,不好意思。