BAEKJOON 2702 - Sixth Grade Math

문제: https://www.acmicpc.net/problem/2702

문제

In sixth grade, students are presented with different ways to calculate the Least Common Multiple(LCM) and the Greatest Common Factor (GCF) of two integers. The LCM of two integers a and b is the smallest positive integer that is a multiple of both a and b. The GCF of two non-zero integers aand b is the largest positive integer that divides both a and b without remainder.

For this problem you will write a program that determines both the LCM and GCF for positive integers.

입력

The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of data sets that follow. Each data set consists of a single line of input containing two positive integers, a and b, (1 ≤ a,b ≤ 1000) separated by a space. 

출력

For each data set, you should generate one line of output with the following values: The data set number as a decimal integer (start counting at one), a space, the LCM, a space, and the GCF.

예제 입력 

3
5 10
7 23
42 56

예제 출력 

10 5
161 1
168 14

힌트

출처

ACM-ICPC > Regionals > North America > Greater New York Region > 2008 Greater New York Programming Contest A번

최대공약수는 Euclidean algorithm 을 사용해 구하고, 최소공배수는 "두 수의 곱 / 최대공약수"인 점을 활용해 풀었습니다.

#include <fstream>
#include <iostream>
#include <cstring>
#include <climits>
#include <algorithm>
 
using namespace std;
 
//GCD is Greatest common divisor
int calcGCD(int a, int b)
{
    int remainder;
    if (a < 1 || b < 1)
        return 0;
 
    if (a < b)
        return calcGCD(b, a);
 
    while ((remainder = a % b) != 0)
    {
        a = b;
        b = remainder;
    }
    return b;
}
 
int main()
{        
    int cases, a, b;
    cin >> cases;
    for (int c = 0; c < cases; c++)
    {
        cin >> a >> b;
        int GCD = calcGCD(a, b);
        cout << a * b / GCD << " " << GCD << endl;
    }
 
    return 0;
}