小乐乐与欧几里得

[编程题]小乐乐与欧几里得

热度指数：79813 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小乐乐最近在课上学习了如何求两个正整数的最大公约数与最小公倍数，但是他竟然不会求两个正整数的最大公约数与最小公倍数之和，请你帮助他解决这个问题。

输入描述:

每组输入包含两个正整数n和m。(1 ≤ n ≤ 10⁹，1 ≤ m ≤ 10⁹)

输出描述:

对于每组输入，输出一个正整数，为n和m的最大公约数与最小公倍数之和。

示例1

输入

10 20

输出

示例2

输入

15 20

输出

算法知识视频讲解

Java

Wilburlee

public static long Gcd(long n, long m){
        while (m != 0){
            long tmp = m;
            m = n % m;
            n = tmp;
        }
        return n;
    }
    public static long Lcm(long n, long m, long gcd){
        return n*m/gcd;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        long n = in.nextInt(), m = in.nextInt();

        //最大公约数，辗转相除法
        long gcd = Gcd(n,m);

        //最小公倍数 : 公式两数乘积除以最大公约数
        long lcm = Lcm(n,m,gcd);

        System.out.println(gcd + lcm);

    }

发表于 2024-07-29 15:51:01 回复(0)

Java

擅长CV工程的浅沫

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
       
        //两数之积
        long nm = (long) n * m;

        //辗转相除法
        int hcf = m;
        while (n % m != 0) {
            hcf = n % m;
            n = m;
            m = hcf;
        }

        // 两数之积 = 最小公倍数 *最大公约数
        long lcm = nm / hcf;

        System.out.print(lcm + hcf);

    }

}

发表于 2023-10-13 21:25:01 回复(0)

Java

圣光·明流火

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        int maxGCD = gcd(num1,num2);
        long minLCM = lcm(num1,num2);
        System.out.println(maxGCD + minLCM);
    }
    //最大公因数
    public static int gcd(int num1,int num2){
       int max = num1 < num2 ? num1 : num2;
       for(int i = max ; i >= 1;i--){
           if(num1 % i == 0 && num2 % i == 0){
               return i;
           }
       }
        return 0;
    }
    //最小公倍数
    public static long lcm(int num1,int num2){
       int min = num1 > num2 ? num1 : num2;
       for(long i = min ; ;i = i + min){
           if(i % num1 == 0 && i % num2 == 0){
               return i;
           }
       }
    }
}

发表于 2022-06-24 10:40:13 回复(0)

Java

欸嘿~

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextInt();
        long m = sc.nextInt();
        long max = m > n ? m : n;
        long min = m < n ? m : n;
        long yin = 0;
        long bei = 0;
        long yu = 1;
        long ji = max * min;
        while (yu != 0) {
            yu = max % min;
            max = min;
            min = yu;
        }
        yin = max;
        bei = ji / yin;
        System.out.print(yin + bei);
    }
}

发表于 2022-06-15 15:34:45 回复(0)

Java

益塘

import java.util.*;
public class Main{
    public static int gcd(int num1, int num2) {
    // 辗转相除法
    int max = num1 > num2 ? num1 : num2;
    int min = num1 < num2 ? num1 : num2;
    if (max % min == 0)
      return min;
    return gcd(max % min, min);
}
    public static int gbs(int num1,int num2){
        int i;
        if(num1 < num2){
             int temp = num1;
             num1 = num2;
             num2 = temp;
         }
        for ( i = num1; i > 0; i++) {
            if(i % num1 == 0 && i %num2 == 0){
                break;
            }
        }
        return i;
    }   
    public static void main(String argv[]){
        Scanner input=new Scanner(System.in);
        int num1=input.nextInt();
        int num2=input.nextInt();
        System.out.print(gcd(num1,num2)+gbs(num1,num2));
    }
    
}

发表于 2022-04-28 15:01:56 回复(0)

Java

牛客916830348号

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long n = scan.nextLong();
        long m = scan.nextLong();
        long num = n * m;//num：两数乘积
       
        //辗转相除法
        while (m != 0) {
            long tmp = n % m;
            n = m;
            m = tmp;
        }
        //n即两数最大公约数 根据最大公约数和最小公倍数的关系  num / n即最小公倍数
        System.out.println(n + (num / n));
    }
}

发表于 2021-10-25 15:54:32 回复(0)

Java

ningjingjing0614

import java.util.Scanner;

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

    public static long gcd(long a, long b) {
        while (a != 0 && b != 0) {
            if (a > b) {
                a %= b;
            } else {
                b %= a;
            }
        }
        return a > b ? a : b;
    }

    public static long lcm(long a, long b) {
        return (a * b) / gcd(a, b);
    }
}

发表于 2021-07-16 22:05:40 回复(0)