侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-11 / 0 评论 / 0 点赞 / 40 阅读 / 514 字 / 正在检测是否收录...

题目

买不到的数目


小明开了一家糖果店。他别出心裁:把水果糖包成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;
            }
        }
    }
}
0

评论区