解法一:
import java.util.Scanner;/**小明开了一家糖果店、把水果糖包成4颗一包和7颗一包的两种。糖果不能拆包卖
小朋友来买糖的时候,他就用两种包装来组合,当然有些糖果数目是无法组合出来的,比如要买10颗糖在这种包装情况下,最大不能买到的数量是17,大于17的任何数字都可以用4和7组合出来 本题的要求是在已知两个包装的数量时,求最大不能组合的出的数字。*///分析:
//ax+by=c,不定方程的解,a=4,b=7,c=17,这种情况下,学院实际上有解,7*2+(7-4)==3*7-1*4
//a,b 互质,一定有解且解的数目无穷
//c是gcd(a,b)的倍数,方程一定有解,而且有无穷多解//条件:一定有解 a,b互质
//条件二:xy都是大于等于0的整数,在这个限定的条件下有的c是无解的,那么c的上界至多是a*bpublic class _买不到的数目 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();System.out.println(a * b - a - b);}}
解法二:
public class _买不到的数字解法二 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int a = sc.nextInt();int b = sc.nextInt();int max=a*b; //最大值Set<Integer> ss=new HashSet<Integer>();//去重//从0开始枚举到maxfor(int x=0; a*x < max; x++) {for(int y = 0; a*x + b*y < max; y++) {ss.add(a*x+b*y);//用不小于0的x和y与系数能组合出来的数加到set中}}for(int i=max-1; i>=0;i--) {if(!ss.contains(i)) {//查找第一个不在set中的值System.out.println(i);break;}}}
}