蓝桥杯2013年第四届真题-买不到的数目 （Java代码）

解题思路:

首先我们要了解，当num能被a和b组合出来时，只有三种情况：

(1）num%a==0

(2)  num%b==0

(3)  num = n*a + m*b  , (n,m = 1,2..........n)

只要弄清这三种原因就好办了，我们可以写一个函数check来判断num是否可以被组合，然后用循环来倒序查找，因为我们知道不能被组合的最大数不可能超过a*b,所以我们可以从a*b开始来递减查找，第一次查出来的就是最大的无法组合数。

注意事项:
当判断第三种条件时，可以让n不断减去一个数b，每减一次就判断n%a是否为零。

import java.util.Scanner;
public class 买不到的数目 {
 
 //判断数n是否可以被a, b组合
 public static boolean Check(int n, int a, int b){
  //当n为a或b的倍数
  if(n%a==0 || n%b==0)
   return true;
  while(n>=a)
   if(n%a==0)
    return true;
   n=n-b; //这一步必须在判断之后，不然核能会出现n<0的情况
  }
  return false;
 }
 public static void test1(){
  Scanner scan = new Scanner(System.in);
  int a = scan.nextInt();
  int b = scan.nextInt();
  if(a>b){
   int temp = a;
   a=b;
   b=temp;
  }
  
  for(int i=a*b; i>0; i--){//倒着查找，第一次查出来的就是最大的无法组合数
   if(!Check(i, a, b)){
    System.out.println(i);
    break;
   }
  }
  
 }
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  test1();
 }
}