[알고리즘/문제풀이/BOJ 1934번] 최소공배수

최소공배수 문제는 최대공약수와 최소공약수의 관계를 활용하여 해결할 수 있다. 두 수를 최대공약수로 나누었을 때의 몫들과 최대공약수를 곱하면 최소공배수를 구할 수 있다는 특성을 이용하여 문제를 해결합니다. 최대공약수는 유클리드 호제법을 이용하여 O(lgn)으로 구할 수 있습니다.

유클리드 호제법에 대한 내용을 다음과 같습니다.

2021.07.10 - [알고리즘/이론] - [알고리즘/이론][정수론] 유클리드 호제법

[알고리즘/이론][정수론] 유클리드 호제법

작성한 코드는 다음과 같습니다.

---

#include<stdio.h>

int T;
int A, B;
int gcd;

int function(int a, int b) {
	int temp;

	if (a > b) {
		temp = a;
		a = b;
		b = temp;
	}

	while(b % a != 0) {
		temp = a;
		a = b % a;
		b = temp;
	}

	return a;
}

int main(void) {
	scanf("%d", &T);

	for (int i = 0; i < T; i++) {
		scanf("%d %d", &A, &B);
		gcd=function(A, B);
		printf("%d\n", gcd * (A / gcd) * (B / gcd));
	}
}

문제의 지문은 다음의 링크에서 확인할 수 있습니다.

https://www.acmicpc.net/problem/1934