[白俊]1934:最小公倍数(JAVA)

質問する

BOJ 1934:最小公倍数-https://www.acmicpc.net/problem/1934

に答える

ユークリッドアーク除算法を用いて2つの自然数a,bの最大公約数(GCD)を求め,2つの数の積を最大公約数(GCD)で除算すると最小公倍数(LCM)となる.
[ユークリッドアーク除算(Euclideanアルゴリズム)]
「2つの自然数の最大公約数(GCD)のアルゴリズムを求めます」
2つの自然数(または正式)a,bについて、aをbで割った残りの数をr(ただし、a>b)と呼ぶと、aおよびbの最大公約数はbおよびrの最大公約数に等しい.GCD(a, b) = GCD(b, a%b)です.bから0を再帰的に繰り返すと,aとbの最大承諾数を求めることができる.
最小公倍数:a * b / GCD(a,b)数学部ではないので、合格したことを証明します.

コード#コード#

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            bw.write(LCM(a,b)+"\n");
        }
        bw.flush();
    }

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

    public static int LCM(int a, int b) {
        return a * b / GCD(a, b);
    }
}

整理する

✔ 알고리즘 분류 - 수학, 정수론, 유클리드 호제법
✔ 난이도 - ⚪ Silver 5

🤦‍♀️ 今日のショベルマン

実際、最小公倍数、最大公約数の問題はユークリッド号の使い方さえ分かれば、すぐに解決できる.でも解くたびに覚えてるよGCD(a, b) = GCD(b, a%b)を知っておく必要があります!

コメントサイト

[ユークリッドのお守り]
https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95