108. 1934(최소공배수)

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

class Main{
	public static void main(String args[])throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			String[] sBits = br.readLine().split(" ");		
			int x = Integer.parseInt(sBits[0]);
			int y = Integer.parseInt(sBits[1]);
			
			sb.append(lcm(x,y)).append("\n");
		}
				
		System.out.println(sb);
	
	}
	
	static int gcd(int x, int y) {
		while(y!=0) {
			int r = x%y;
			x = y;
			y = r;
		}
		return x;
	}
	
	static int lcm(int x, int y) {
		return x * y / gcd(x,y);
	}
}

문제요약

최소 공배수를 구하는 문제

설명

gcd => 최대 공약수

lcm => 최소 공배수

 

최대공약수는 x % y 를 진행하다가 0이나올 때 x의 값이 최대 공약수이다.

예를 들어 24 18이 들어오면,

1)

24 % 18 = 6 = r

x = 18

y = 6

 

2) 18 % 6 = 0 = r

x = 6

y = 0

 

y가 0이 되었으므로 x값을 리턴한다.

 

최소 공배수는 x와 y를 곱한 값에서 최대공약수로 나누어지면 값이 나온다.