백준 10253번 헨리 C++

출처 : https://www.acmicpc.net/problem/10253

단위분수의 분모를 정하는 것이 이 문제의 핵심인 것 같다.

분모에서 분자를 나눈 값의 나머지가 0이라면 분모 / 분자 를 다음 단위분수의 분모로 하였고,

0이 아니라면 (분모 / 분자 ) + 1 을 다음 단위분수의 분모로 정하였다.

 

첫번째 예제로 예를 들자면 23 / 4 = 5 ... 3 이기 때문에 다음 단위분수의 분모는 5 + 1 = 6 이고

1 / 6 과 4 / 23 을 통분하면 23 / 138 과 24 / 138 이 된다. 이렇게 구하는 것이 분자 / 분모 보다 작은 단위분수 중 가장 큰 값 이라고 생각했다. 만약 단위분수의 분모를 그냥 1씩 증가시키면서 계산을 한다면 시간초과가 날 것이다.

 

그리고 오버플로우도 조심해서 풀어야 한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

ll GetGCD(ll a, ll b) {
	if (b == 0) return a;
	else return GetGCD(b, a % b);
}

ll GetLCM(ll a, ll b) {
	ll GCD = GetGCD(a, b);
	return a * (b / GCD);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int t;
	cin >> t;
	while (t--) {
		ll bunja, bunmo;
		cin >> bunja >> bunmo;
		ll n = 2;
		while (bunja != 0) {
			if (GetGCD(bunmo, bunja) == bunja) n = bunmo / bunja;
			else n = (bunmo / bunja) + 1;
			ll newBunmo = GetLCM(n, bunmo);
			ll muled = newBunmo / n;
			ll newBunja = bunja * (newBunmo / bunmo);
			newBunja -= muled;
			if (newBunja == 0) break;
			ll gcd = GetGCD(newBunja, newBunmo);
			bunja = newBunja / gcd;
			bunmo = newBunmo / gcd;
		}
		cout << bunmo << "\n";
	}
};