https://www.acmicpc.net/problem/5347
두 수 a와 b가 주어졌을 때, a와 b의 최소 공배수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 n이 주어진다. 다음 n개 줄에는 a와 b가 주어진다. a와 b사이에는 공백이 하나 이상 있다. 두 수는 백만보다 작거나 같은 자연수이다.
각 테스트 케이스에 대해서 입력으로 주어진 두 수의 최소공배수를 출력한다.
유클리드 호제법을 사용해서 최대 공약수를 구한다.
구한 최대 공약수를 이용해서 입력으로 들어온 a와 b를 나눈 나머지를 구해서 최소공배수를 구한다.
최소 공배수를 출력한다.
#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;
}
유클리드 호제법을 알면 딱히 어려울 게 없는 문제였던 것 같다.