C++에서 유리수의 최소공배수(LCM) 구하기

C++에서 유리수의 최소공배수(LCM) 구하기

이 글에서는 여러 개의 유리수가 주어졌을 때 그 최소공배수(LCM)를 구하는 방법을 알아봅니다. 예를 들어 유리수 목록이 {2/7, 3/14, 5/3}과 같다면, 이들의 LCM은 30/1이 됩니다.

유리수 LCM의 기본 원리

정수와 달리 유리수의 LCM은 분자와 분모를 각각 따로 처리해야 한다는 점이 특징입니다. 핵심 아이디어는 다음과 같습니다.

• 모든 분자의 LCM(최소공배수)을 구합니다.
• 모든 분모의 GCD(최대공약수)를 구합니다.
• 분자의 LCM을 분모의 GCD로 나누면 유리수 전체의 LCM이 됩니다.

이를 수식으로 나타내면 다음과 같습니다.

$$LCM = \frac{\text{모든 분자의 LCM}}{\text{모든 분모의 GCD}}$$

예시 {2/7, 3/14, 5/3}에 적용해 보면, 분자 2, 3, 5의 LCM은 30이고 분모 7, 14, 3의 GCD는 1이므로 최종 결과는 30/1이 됩니다.

예제 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 두 정수의 최소공배수(LCM)를 구하는 함수
int LCM(int a, int b) {
    return (a * b) / (__gcd(a, b));
}

// 모든 분자의 LCM을 구하는 함수
int numeratorLCM(vector<pair<int, int>> vect) {
    int result = vect[0].first;
    for (int i = 1; i < vect.size(); i++)
        result = LCM(vect[i].first, result);
    return result;
}

// 모든 분모의 GCD를 구하는 함수
int denominatorGCD(vector<pair<int, int>> vect) {
    int res = vect[0].second;
    for (int i = 1; i < vect.size(); i++)
        res = __gcd(vect[i].second, res);
    return res;
}

// 유리수 전체의 LCM을 '분자/분모' 형태로 출력하는 함수
void rationalLCM(vector<pair<int, int>> vect) {
    cout << numeratorLCM(vect) << "/" << denominatorGCD(vect);
}

int main() {
    vector<pair<int, int>> vect;
    vect.push_back(make_pair(2, 7));
    vect.push_back(make_pair(3, 14));
    vect.push_back(make_pair(5, 3));
    cout << "유리수의 LCM: ";
    rationalLCM(vect);
}

실행 결과

유리수의 LCM: 30/1

코드 설명

• LCM(a, b): 두 정수의 최소공배수를 구합니다. 두 수의 곱을 최대공약수로 나누는 방식으로 계산됩니다.
• numeratorLCM(): 벡터에 담긴 모든 분자를 순회하면서 누적 LCM을 계산합니다.
• denominatorGCD(): 모든 분모를 순회하면서 누적 GCD를 계산합니다.
• rationalLCM(): 앞서 구한 두 값을 '분자/분모' 형태로 출력합니다.

참고: 예제에서 사용한 __gcd는 GCC 계열 컴파일러가 제공하는 비표준 함수입니다. C++17 이상 환경이라면 <numeric> 헤더의 표준 함수인 std::gcd를 사용하는 것이 바람직합니다.