【数学, 暴力】买不到的数目【蓝桥杯】

题目

买不到的数目

---

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

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

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

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

输入：

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

输出：

• 一个正整数，表示最大不能买到的糖数

示例 1：

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

示例 2：

用户输入：
3 5
程序应该输出：
7

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

解题

方法一：数学 暴力

思路

代码

public class Main {
    // ax+by=C, a=4,b=7,C=17 这种情况下, xy实际上有解: 7*2 + (7-4) == 3*7 - 1*4 => x=-1,y=3
    // a,b互质, 一定有解且解的数目无穷
    // C是gcd(a,b)的倍数, 方程一定有解, 且有无穷多解

    // 条件1: 一定有解 => a,b互质
    // 条件2: x,y都是大于0的整数
    // 在这两个条件下有的C是无解的, 那么C的上界至多是lcm(a*b) == a*b
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt();
        int lcm = a * b;
        Set<Integer> amountSet = new HashSet<>();
        for (int x = 0; a * x <= lcm; x++) {
            for (int y = 0; a * x + b * y <= lcm; y++) {
                amountSet.add(a * x + b * y);
            }
        }
        for (int i = lcm; i >= 0; i--) {
            if (!amountSet.contains(i)) {
                System.out.println(i);
                break;
            }
        }
    }
}