标题：买不到的数目
小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。 输入： 两个正整数，表示每种包装中糖的颗数(都不多于1000) 要求输出： 一个正整数，表示最大不能买到的糖数 不需要考虑无解的情况 例如： 用户输入： 4 7 程序应该输出： 17 再例如： 用户输入： 3 5 程序应该输出：7
分析：
这道题的一般解法不难想到，这两天刚好学习了扩展的欧几里得算法，所以觉得这道题可以借助该算法来提高性能，因为刚接触该算法一知半解，经过艰苦的测试，初步得到了一种解法，不过不敢保证一定正确，所以贴出来，如果哪位发现有错，请麻烦告知一声，我好修改或者删掉代码。
首先理论依据来自该篇文章：
该文章中有这样一个等式：a(x+qb)+b(y-qa)=c; q为任意整数
在代码中，m对应这里的a，n对应这里的b
从该等式中，我们可以得到：x+qb>=0 ; y-qa>=0 （1）
其中，x=(c/d)*x‘ y=(c/d)*y'
其中d=1，所以x=c*x' ,y=c*y'
对于x'和y'可以通过扩展的欧几里得算法求得，
则 式子（1）可以转换成：
c*x'+qb>=0; （2）
c*y'-qa>=0; （3）
满足以上两个式子，未知变量有c和q，验算了好久，还是不能在这里进一步直接得到c的值，所以暂时只能退而一个一个验证c是否满足条件了，
如果y‘>0，那么x'一定<0，结合（2）（3），(将a替换成m，b替换成n)
可以得到：
-m*x'*q<=|x'*y'*c|<=n*y'*q (4)
到了这里就可以直接测试c的取值了，当c取什么值，使得q无解（q是整数）
如 m=3，n=4 （x‘=-1，y’=1）
根据（4）有：
3q<=c<=4q （这里如果能够直接得出c的值就不用去测试了，但是暂时想不到怎么直接得出c的值）
当c取什么值，使得q无解，c从m*n开始向下递减，
当c=12,11,10,9,8,7,6,的时候，q都有解
当c=5的时候，q是无解的
所以c=5是对应的答案
以上是y‘>0的情况，如果y'<0，则对应的（4）式为：
-n*y'*q<=|x'*y'*c|<=m*x'*q （5）
如：m=4，n=7 （x'=2,y'=-1）
根据（5）式有：
7q<=2c<=8q
当c=28~18 ,q都有解
当c=17 ，q无解
所以c=17为结果
以下就是对应的java代码：
import java.util.Scanner;public class ys_cbk_08 { // 使用扩展的欧几里得算法 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // 如果两个数的最大公约数不是1，则无解 int m = scanner.nextInt(), n = scanner.nextInt(); // 1.求满足m*x+n*y=gcd(m,n)等式的x,y的解 // 求最大公约数，同时求,x,y的值 int gcd = gcd(m, n); if (gcd != 1) { System.out.println("无解"); return; } if (y < 0) {//这里的y对应分析中的y’ int a = -n * y; int b = m * x; int c = 0; for (int i = n * m; i >= 1; i--) { c = -x * y * i; //测试c if ((c / a) * b < c) { System.out.println(i); break; } } } else { int a = -m * x; int b = n * y; int c = 0; for (int i = n * m; i >= 1; i--) { c = -x * y * i; if ((c / a) * b < c) { System.out.println(i); break; } } } } private static int x; private static int y; /** * 使用扩展欧几里得算法求最大公约数及其对应的x,y值 * @param m * @param n * @return */ public static int gcd(int m, int n) { // 方法1，递归 // if(n==0){ // x=1; // y=0; // return m; // } // int d=gcd(n,m%n); // int tmp=x; // x=y; // y=tmp-m/n*y; // return d; // 引用：http://www.cnblogs.com/frog112111/archive/2012/08/19/2646012.html // 方法2，非递归 int x1, y1, x0, y0; x0 = 1; y0 = 0; x1 = 0; y1 = 1; x = 0; y = 1; int r = m % n; int q = (m - r) / n; while (r != 0) { x = x0 - q * x1; y = y0 - q * y1; x0 = x1; y0 = y1; x1 = x; y1 = y; m = n; n = r; r = m % n; q = (m - r) / n; } return n; }} 输入：
22 23
输出：
461