2609번 최대공약수와 최소공배수

유클리드 알고리즘이다.

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

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
// 최소공배수 * 최대공약수 = p * q
 
int gcd(int p, int q)
{
    if (q == 0) return p;
    return gcd(q, p%q);
}
 
int main(void)
{
    int p = 0, q = 0;
 
    scanf("%d %d", &p, &q);
 
    int GCD = gcd(p, q);
 
    printf("%d\n", GCD);
    printf("%d\n", p*q / GCD);
 
    return 0;
}