백준] 1735 - 분수 합

시간 제한 : 2초

메모리 제한 : 128MB

입력

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

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

소스코드

#include <iostream>
using namespace std;
int gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		gcd(b, a%b);
}
int main(void)
{
	int a1, a2, b1, b2, lcm, sum, ki;
	cin >> a1 >> a2;
	cin >> b1 >> b2;
	if (a2 > b2)
		lcm = gcd(a2, b2);
	else
		lcm = gcd(b2, a2);
	lcm = a2*b2 / lcm;
	a1 = (lcm / a2)*a1, b1 = (lcm / b2)*b1;
	sum = a1 + b1;
	if (sum > lcm)
		ki = gcd(sum, lcm);
	else
		ki = gcd(lcm, sum);

	cout << sum / ki << ' ' << lcm / ki;
}

Tip

유클리드 호제법을 이용한 수학 문제