蓝桥杯-买不到的数目

本文转载自：http://blog.csdn.net/keepthinking_/article/details/9262825

 

标题：买不到的数目

    小明开了一家糖果店。他别出心裁：把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖。

    小朋友来买糖的时候，他就用这两种包装来组合。当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。

    你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。大于17的任何数字都可以用4和7组合出来。

    本题的要求就是在已知两个包装的数量时，求最大不能组合出的数字。

输入：
两个正整数，表示每种包装中糖的颗数(都不多于1000)

要求输出：
一个正整数，表示最大不能买到的糖数

不需要考虑无解的情况

例如：
用户输入：
4 7
程序应该输出：
17

再例如：
用户输入：
3 5
程序应该输出：

7

分析：

这道题的一般解法不难想到，这两天刚好学习了扩展的欧几里得算法，所以觉得这道题可以借助该算法来提高性能，因为刚接触该算法一知半解，经过艰苦的测试，初步得到了一种解法，不过不敢保证一定正确，所以贴出来，如果哪位发现有错，请麻烦告知一声，我好修改或者删掉代码。

首先理论依据来自该篇文章：http://www.cppblog.com/yuanyuelang/articles/95378.html

该文章中有这样一个等式：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