Tìm BCNN của các số hữu tỷ trong C++

Chúng ta sẽ xem cách tìm BCNN (Bội chung nhỏ nhất) của các số hữu tỷ. Cho một danh sách các số hữu tỷ, ví dụ {2/7, 3/14, 5/3}, thì BCNN sẽ là 30/1.

Để giải bài toán này, ta tính BCNN của tất cả các tử số, sau đó tính UCLN (Ước chung lớn nhất) của tất cả các mẫu số. BCNN của các số hữu tỷ sẽ là:

$$BCNN = \frac{BCNN\:của\:tất\:cả\:tử\:số}{UCLN\:của\:tất\:cả\:mẫu\:số}$$

Ví dụ minh họa

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

int LCM(int a, int b) {
    return (a * b) / (__gcd(a, b));
}

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;
}

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;
}

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 << "BCNN của các số hữu tỷ: ";
    rationalLCM(vect);
    return 0;
}

Kết quả

BCNN của các số hữu tỷ: 30/1