本文转载自: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
相关推荐
蓝桥杯-嵌入式-06-ADC
蓝桥杯-嵌入式-05-IIC
蓝桥杯-嵌入式-03-LCD
蓝桥杯-嵌入式-04-USART
蓝桥杯-习题.rar
蓝桥杯-嵌入式-02-LED-KEY
蓝桥杯--单片机资源数据包_2020
蓝桥杯-历届试题
蓝桥杯 -- 第十一届嵌入式设计与开发科目模拟试题
蓝桥杯-叶海荣课件.pptx,里面的内容写的很好,参加蓝桥杯的同学都可以看看
蓝桥杯-2018-省赛-Java语言大学C组
蓝桥杯-C语言图形输出
蓝桥杯-2016复习参考-结果填空题
蓝桥杯-2016复习参考-代码填空题
C++语言蓝桥杯-杨辉三角
蓝桥杯-全套习题带答案蓝桥杯练习题库,从官网获取,包含vip试题。蓝桥杯练习题库,从官网获取,包含vip试题
蓝桥杯-独立农作物.cpp
蓝桥杯-省赛-Java语言大学A组.doc
第四届蓝桥杯真题\2013第四届蓝桥杯-CC++高职高专组 真题
蓝桥杯-十六进制转八进制,题目分析讲解,100000长度的十六进数巧妙制转八进制数,C代码实现展示