题目描述
小明开了一家糖果店。他别出心裁：把水果糖包成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代码（方法一）
代码语言：javascript复制#include <bits/stdc .h>
using namespace std;
int main() {
int m,n;
cin>>m>>n;
cout<<m*n-m-n;
return 0;
}AC代码（方法二）
代码语言：javascript复制#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;
}
}
