C++ 기약분수

알고리즘

C++ 기약분수

Chars4785 2019. 1. 10. 11:32

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 공백으로 구분하여 순서대로 출력한다.

예시

2 7
3 5

31 35

#include <iostream>
#include <vector>

using namespace std;

int getGCD(int a,int b)
{   
    int GDC;

   while(1)
   {
      int r = a % b;

      if( r == 0)
      {
         GDC = b;
         break;
      }

      a = b;
      b = r;
   }

    return GDC;
}

int getLCM(int A,int B,int GDC)
{
    int LCM;
    
    LCM = (A/GDC) * (B/GDC) * GDC;
    
    return LCM;
}

int main() {


    int fraction[2][2];

    for(int i =0;i<2;i++)
        for(int j=0;j<2;j++)
            cin >>fraction[i][j];

     
    int LCM = getLCM(fraction[0][1],fraction[1][1]
                ,getGCD(fraction[0][1],fraction[1][1]));
    
    int result = fraction[0][0]*(LCM / fraction[0][1])
                +fraction[1][0]*(LCM / fraction[1][1]);
    
    int GCD = getGCD(result,LCM);
    
    result /= GCD;
    LCM /= GCD;

    cout<< result<<" "<< LCM;


    return 0;
}