目录
题目描述
思路分析
AC代码（方法一）
AC代码（方法二）
题目描述
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。
小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。
你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。
本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。
输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)
要求输出：
一个正整数，表示最大不能买到的糖数
不需要考虑无解的情况
例如：
用户输入：
4 7
程序应该输出：
17
再例如：
用户输入：
3 5
程序应该输出：
7
思路分析
方法一：
图论知识：
自然数a,b互质,则不能表示成ax+by（x,y为非负整数）的最大整数是ab-a-b。
极其NB的性质，高级的数学定理搞定一切美妙的算法。
方法二：
数学知识：
a和b线性组合不能表示的数字介于a+b-1和a和b的最小公倍数之间。
这里需要暴力遍历，其实这个性质就解决了遍历的上限。
我们需要三个函数，一个求最大公因数，一个求最小公倍数，一个检查是否不能由a和b表示。
我的疑惑
有没有懂哥解释一下为什么这两个性质是成立的？
AC代码（方法一）
#include <bits/stdc++.h>
using namespace std;
int main() {
int m,n;
cin>>m>>n;
cout<<m*n-m-n;
return 0;
}
AC代码（方法二）
#include <bits/stdc++.h>
using namespace std;
int GCD(int a, int b) {
while (a % b) {
int temp = a % b;
a = b;
b = temp;
}
return b;
}
int LCM(int &a, int &b) {
return a * b / GCD(a, b);
}
bool Check(int &test, int &a, int &b) {
for (int i = 0; i <= b; i++)
for (int j = 0; j <= a; j++)
if (test == i * a + j * b)
return false;
return true;
}
int main() {
int m, n, i;
cin >> m >> n;
for (i = LCM(m, n) - 1; i >= m + n - 1; i--)
if (Check(i, m, n)) {
cout << i;
return 0;
}
}
