https://www.acmicpc.net/problem/1735
Solved
✔ 알고리즘 분류: 수학, 정수론, 유클리드 호제법
✔ 유클리드 호제법: 최대공약수를 구하는 알고리즘
유클리드 호제법
1. 두 수 a,b가 있고, 두 수의 최대공약수를 구하고자 한다.
2. a를 b로 나눈다. 나머지 r이 나온다.
3. 나머지 r이 0이라면 b가 최대공약수이다. 그렇지않다면 이번에는 b를 r로 나눈다.
3번에서 b를 r로 나눈 나머지가 0이면 r(나눈값)이 최대공약수이다. 그렇지 않다면 2~3번을 반복한다.
using namespace std;
#include <iostream>
int gcd(int a, int b) {
//3. 나머지 r이 0이라면 b가 최대공약수이다. 그렇지않다면 이번에는 b를 r로 나눈다.
if (b == 0) return a;
//2. a를 b로 나눈다. 나머지 r이 나온다.
return gcd(b, a % b);
}
int main() {
int a, b, c, d, p, q, g;
cin >> a >> b >> c >> d;
p = a * d + b * c; //분자
q = b * d; //분모
//1. 두 수 a(p),b(q)가 있고, 두 수의 최대공약수를 구하고자 한다.
g = gcd(p, q); //분자와 분모의 최대 공약수
cout << p / g << ' '<<q / g << '\n';
}