[白俊]#1934最小公倍数

📝 質問する

2つの自然数AとBについて、Aの倍数でありBの倍数である自然数をAとBの公倍数と呼ぶ.この公倍数の中で最小の数を最小公倍数と呼ぶ.例えば、6及び15の公倍数は30、60、90等であり、最小公倍数は30である.
2つの自然数AとBが与えられた場合、AとBの最小公倍数を求めるプログラムを作成してください.

入力

第1行は、試験例の個数T(1≦T≦1000)を与える.2行目からT行にまたがり、AとBが与えられる.(1 ≤ A, B ≤ 45,000)

💻 しゅつりょく

1行目から、T行入力AとBの最小公倍数の順に1行ずつ出力します.

📃 入力例

3
1 45000
6 10
13 17

📃 サンプル出力

45000
30
221

🔍マイコード

package com.focusonmx.baekjoon.CodeplusBasicMath;

import java.util.Scanner;

public class B1934 {
	static int N;
	static int a;
	static int b;
	static int GCD;
	static int LCM;
	
	public static int Euclidean(int a, int b) {
		int r;
		while(b!=0) {
			r=a%b;
			a=b;
			b=r;
		}
		return a;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		N= sc.nextInt();
		
		for(int i=0;i<N;i++) {
			a= sc.nextInt();
			b=sc.nextInt();
			GCD=Euclidean(a,b);
			LCM=(a/GCD)*(b/GCD)*GCD;
			System.out.println(LCM);
		}
		
		
	}

}

📖 学識

ユークリッドアークほう

2つの正の整数あるいは2つの多項式の最大の公因数の方法を求めます
2つの正の整数a,b(a>b)a,b(a>b)a,b(a>b)について
a=bq+r (0≤rすなわち、a、ba、ba、bの最大承諾数は、b、rb、rb、rの最大承諾数に等しい.
つまり.
gcd⁡(a, b)=gcd⁡(b, r)gcd(a,b)=gcd(b,r).r=0\gcd\left(a,\b\right)=\gcd\left(b,\r\right)gcd(a, b)=gcd(b, r). r=0gcd(a, b)=gcd(b, r)gcd(a,b)=gcd(b,r).r=0
もしそうなら、a,ba,ba,bの最大公約数はbbbになります.

例(12345および1234の最大公約数)

2つの数の最大承諾数は1です.

複文

def Euclidean(a, b):
   while b != 0:
       r = a % b
       a = b
       b = r
   
   return a   

複文

def Euclidean(a, b):

r = b % a

if r == 0:
 return a

else:
 return Euclidean(r, a)

時間の複雑さを考慮して、できるだけ複文を書かないでください.