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

解题思路:

    之前不太会做这个题目，在百度上看到大神的思路，感觉很好。

    find1（）这个方法求出来的是最大公因数，find2()求出来的是最小公倍数。可能很多人不懂上限为什么是最小公倍数。就假如4 和7，最大公倍数28肯定能用4和7（4个7或者7个4）组成,；然后想29时，两个4是8，比7多1，那把一个7换成两个4；在想30，两个7代替3个4.往后推，不管这i个4和j个7怎么变，都可以找到。

你肯定不能一下想到剩下的每个是由几个i和几个j组成，需要配，但这么推好几个都是成立的。

    find3()来找不能配到的整数，首先想到的就是公倍数逐个减1来验证，一旦可以整除4或7，直接减1。减后的数不能整除4或者7，就一定需要i个4或者j个7组成，那就直接减第一个数，减到可以整除4或7，若减到小于0都无法整除，说明它就无法有i个4或j个7组成。

注意事项:有问题，欢迎提问。

参考代码:

import java.util.Scanner;

public class Main {

public static int find1(int a,int b){

 if(a==0)

 return b;

  if(b==0)

 return a;

  return find1(b,a%b);  

}

public static int find2(int a,int b){

  int num=a*b/find1(a,b);

  return num;

}

public static int find3(int a,int b){

  int m = find2(a,b);

  int c = m;

  while(m>0){

   if(m%a==0||m%b==0)

   m=--c;

   else

   m-=a;

   }

  return c;

}

public static void main(String[] args) {

  Scanner scanner = new Scanner(System.in);

      int a =scanner.nextInt();

      int b =scanner.nextInt();

      System.out.println(find3(a,b));;

}

}