C++에서 유리수의 LCM 찾기

여기서 우리는 유리수의 LCM을 찾는 방법을 볼 것입니다. 유리수 목록이 있습니다. 목록이 {2/7, 3/14, 5/3}과 같다고 가정하면 LCM은 30/1이 됩니다.

이 문제를 해결하려면 모든 분자의 LCM을 계산하고 모든 분모의 gcd를 계산한 다음 유리수의 LCM을 계산하면 다음과 같습니다. -

$$LCM =\frac{LCM\:of\:all\:𝑛𝑢𝑚𝑒𝑟𝑎𝑡𝑜𝑟𝑠}{GCD\:of\:all\:𝑑𝑝𝑛𝑜𝑚𝑖𝑝

예시

#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 << "LCM of rational numbers: "; rationalLCM(vect);
}

출력

LCM of rational numbers: 30/1