【最小公倍数, 暴力】核桃的数量【蓝桥杯】

题目

核桃的数量

---

小张是软件项目经理，他带领3个开发组。工期紧，今天都在加班呢。为鼓舞士气，小张打算给每个组发一袋核桃（据传言能补脑）。他的要求是：

　　1. 各组的核桃数量必须相同 　　2. 各组内必须能平分核桃（当然是不能打碎的） 　　3. 尽量提供满足1,2条件的最小数量（节约闹革命嘛）

输入：

• a b c a,b,c都是正整数，表示每个组正在加班的人数，用空格分开（a,b,c<30）

输出：

• 一个正整数，表示每袋核桃的数量。

示例 1：

用户输入：
2 4 5
程序输出：
20

示例 2：

用户输入：
3 1 1
程序输出：
3

资源限制

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

解题

方法一：暴力

思路

循环从 1 到 a*b*c ，输出其中第一个可以被 a, b, c同时整除的数

代码

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
        for (int product = 1; product <= a * b * c; product++) {
            if (product % a == 0 && product % b ==  0 && product % c == 0) {
                System.out.println(product);
                break;
            }
        }
    }
}

方法一：最小公倍数

思路

由题意，直接求出 a, b, c 的最大公倍数即为核桃的数量

代码

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(lcm(sc.nextInt(), sc.nextInt(), sc.nextInt()));
    }

    private static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    private static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    private static int lcm(int a, int b, int c) {
        return lcm(lcm(a, b), lcm(b, c));
    }
}