[백준 2702] 초6 수학 (C#, C++) - soo:bak

문제 링크

2702번 - 초6 수학

설명

두 수에 대해 최대공약수(GCD)와 최소공배수(LCM)를 동시에 구하는 문제입니다.

• 두 수 A, B가 주어졌을 때,
  
  • 최대공약수(GCD)는 두 수의 공통된 약수 중 가장 큰 수를 의미합니다.
    
  • 최소공배수(LCM)는 두 수의 공통된 배수 중 가장 작은 수를 의미합니다.
    
• 이 문제에서는 최소공배수 먼저, 최대공약수 그다음 순으로 한 줄에 출력해야 합니다.
  

수학적 개념

• 유클리드 호제법을 사용하여 최대공약수 G를 구할 수 있고,
  

  \(\text{LCM}(A, B) = \frac{A \times B}{\text{GCD}(A, B)}\)
  

  의 공식으로 최소공배수를 계산할 수 있습니다.
  

• 이때 곱셈 결과가 큰 경우를 대비해 오버플로우에 주의해야 합니다.

참고 : GCD(최대공약수)와 유클리드 호제법의 원리 - soo:bak

---

접근법

• 테스트케이스 개수를 먼저 입력받습니다.
  
• 각 테스트케이스마다 두 정수를 입력받고,
  
  • 최대공약수는 유클리드 알고리듬으로 재귀적으로 계산합니다.
    
  • 최소공배수는 두 수의 곱을 최대공약수로 나누어 구합니다.
    
• 최소공배수를 먼저 출력한 후, 최대공약수를 출력해야 합니다.
  

---

Code

[ C# ]

using System;

class Program {
  static int GCD(int a, int b) {
    if (b == 0) return a;
    return GCD(b, a % b);
  }

  static void Main() {
    int t = int.Parse(Console.ReadLine()!);
    while (t-- > 0) {
      var input = Console.ReadLine()!.Split();
      int a = int.Parse(input[0]);
      int b = int.Parse(input[1]);
      int g = GCD(a, b);
      long lcm = (long)a * b / g;
      Console.WriteLine($"{lcm} {g}");
    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int cntCases; cin >> cntCases;
  for (int i = 0; i < cntCases; i++) {
    int num1, num2; cin >> num1 >> num2;
    int gcdVal = gcd(num1, num2);
    int lcm = num1 * num2 / gcdVal;
    cout << lcm << " " << gcdVal << "\n";
  }

  return 0;
}