3943: 蓝桥杯C++真题（13）：买糖果
Description
题目描述：
某商店将一种糖果按照数量打包成N和M两种规格来售卖(N和M为互质数，且N和M有无数包)。这样的售卖方式会限制一些数量的糖果不能买到。给出N和M的值，请你计算出最多不能买到的糖果数量。
例如：
当N = 3, M = 5, 3 和 5 为互质数，不能买到的糖果数量有1, 2, 4, 7，最多不能买到的糖果数量就是7, 7之后的任何数量的糖果都是可以通过组合购买到的。
Input
输入两个正整数N,M (2 < N < M < 100,N和M为互质数)，表示两种规格的糖果数量，正整数之间一个空格隔开！
Output
输出一个整数，表示最多不能买到的糖果数量：
Sample Input Copy
3 5Sample Output Copy
7HINT
如何证明: 给定两个互质的正整数a，b，a*b以上的数字一定可以 由若干个a和若干个b组合出来.
要证明这个结论，我们需要利用互质数的性质。
由于a和b是互质的，所以它们的最大公约数gcd(a, b) = 1。因此，由裴蜀定理可得存在整数x和y，使得ax + by = 1。我们可以对这个等式进行变形，得到：
ax + by = 1 ax(a(b-1) + y) + b(-b(x-1)) = ab - 1
因为x、y、a、b都是整数，所以ax(a(b-1) + y)和b(-b(x-1))也是整数。因此，我们可以把右边的ab - 1表示成若干个a和b的和，即：
ab - 1 = ax(a(b-1) + y) + b(-b(x-1)) + kab
其中k为一个整数。我们可以进一步变形，得到：
ab = a(bx + k) + b(ay - b(x-1))
因此，我们证明了对于任意大于等于ab的整数，都可以表示成若干个a和b的和的形式。具体地，设这个整数为c，则我们可以先找到一个最大的k，使得c - ak大于等于b，然后我们可以用若干个a表示出c - ak，再加上k个b，即可表示出c。由于c大于等于ab，所以这个表示一定是合法的。
因此，我们证明了结论：给定两个互质的正整数a和b，a*b以上的任意整数都可以表示成若干个a和b的和。