[백준 1934] 최소공배수 (C#, C++) - soo:bak

문제 링크

1934번 - 최소공배수

설명

두 자연수의 최소공배수(Least Common Multiple, LCM)를 구하는 문제입니다.

최소공배수란?

• 두 수 A와 B의 공배수 중에서 가장 작은 수를 말합니다.
  
• 최소공배수는 두 수의 곱을 최대공약수(GCD)로 나누어 구할 수 있습니다.
  
  

접근법

1. 유클리드 호제법을 사용하여 두 수의 최대공약수(GCD)를 구합니다.
   
2. 두 수의 곱을 GCD로 나누어 최소공배수(LCM)를 구합니다.
   

예제 시뮬레이션

입력:

3
1 45000
6 10
13 17

과정:

1. 1과 45000의 LCM → 45000
   
2. 6과 10의 LCM → 30
   
3. 13과 17의 LCM → 221
   

출력:

45000
30
221

---

Code

[ C# ]

using System.Text;

namespace Solution {
  class Program {

    static int GetGcd(int a, int b) => b == 0 ? a : GetGcd(b, a % b);

    static void Main(string[] args) {
      var t = int.Parse(Console.ReadLine()!);
      var sb = new StringBuilder();

      for (int i = 0; i < t; i++) {
        var input = Console.ReadLine()!.Split();
        var a = int.Parse(input[0]);
        var b = int.Parse(input[1]);
        sb.AppendLine((a * b / GetGcd(a, b)).ToString());
      }

      Console.Write(sb);
    }
  }
}

[ C++ ]

#include <iostream>

using namespace std;

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

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

  int t; cin >> t;
  while (t--) {
    int a, b; cin >> a >> b;
    cout << (a * b) / getGcd(a, b) << "\n";
  }

  return 0;
}