历届试题核桃的数量

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

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

输入格式输入包含三个正整数a, b, c，表示每个组正在加班的人数，用空格分开（a,b,c<30）输出格式输出一个正整数，表示每袋核桃的数量。样例输入1 2 4 5 样例输出1 20 样例输入2 3 1 1 样例输出2 3

解题思路: 求两个数的最大公约数用辗转相除法。思路如下：

代码语言：javascript复制

GCD(int a,int b){
        int gcd;
        while(b != 0){
            gcd = a % b;
            a = b;
            b = gcd;
        }
        gcd = a;
        return gcd;
    }

那么两个数的最小公倍数gcm = a*b/GCD(a,b)。进行递推：n个数的最小公倍数为n个数的乘积/n-1组不同数的最大公约数的乘积。

AC代码如下:

代码语言：javascript复制

import java.util.Scanner;

public class Main {
    static int A;
    static int B;
    static int C;

    public static int GCD(int a,int b){
        int gcd;
        while(b != 0){
            gcd = a % b;
            a = b;
            b = gcd;
        }
        gcd = a;
        return gcd;
    }

    public static int GCM(int a,int b){
        int tmp1 = a;
        int tmp2 = b;
        int gcd = GCD(tmp1,tmp2);
        int gcm = a*b/gcd;
        return gcm;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        A = in.nextInt();
        B = in.nextInt();
        C = in.nextInt();
        int gcd1 = GCD(A,B);
        int gcd2 = GCD(B,C);
        int gcm = A*B*C/(gcd1*gcd2);
        System.out.print(gcm);
        in.close();
    }

}

项目经理

0 人点赞

历届试题 核桃的数量

历届试题核桃的数量