백준 알고리즘 5347번 : LCM

문제 링크

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

제한

문제

두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.

출력

각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.

예제 입력 및 출력

풀이

1. 유클리드 호제법을 사용해서 최대 공약수를 구한다.

2. 구한 최대 공약수를 이용해서 입력으로 들어온 a와 b를 나눈 나머지를 구해서 최소공배수를 구한다.

3. 최소 공배수를 출력한다.

풀이 코드

#include <stdio.h>

int gcd(int a,int b){
  if(b == 0){
    return a;
  }
  return gcd(b,a%b);
}

int main(){
  int t =0;
  scanf("%d",&t);
  for(int i = 0; i < t; i++){
    int a = 0,b = 0;
    scanf("%d %d",&a,&b);
    int large = gcd(a,b);
    printf("%d\n",large*(a/large)*(b/large));
  }
  return 0;
}

인증

복기

유클리드 호제법을 알면 딱히 어려울 게 없는 문제였던 것 같다.