BOJ-10253 헨리

접근

• 방정식과 시간복잡도에 대한 고려를 해야하는 문제였다.

• 먼저 헨리식 표현법의 첫번째 수를 구하는 방법은 아래와 같다.

• $\frac{1}{x^{1}} \leq \frac{a}{b}$

• 따라서 2부터 값을 대입하는 부분을 $O(n)$에서 $O(1)$로 줄여야했다.

• 식을 정리하여 $b/a \leq x^1$

• $x^1$을 구한후 a,b에 각각 값을 갱신해주고 a가 1이 될때 까지 반복하면 된다.

• $\frac{5}{7} = \frac{1}{2} +\frac{?}{?}$

• 이때 a와 b가 기약분수 꼴이 아닌 결과가 나올때도 있는데, 이 문제는 gcd(a,b)를 각a,b에 나눠주면서 해결할 수 있었다.

코드(C++)

#include <iostream>
#define FIO  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
using namespace std;
typedef long long ll;
ll t,a,b;
ll gcd(ll a,ll b){ return b ? gcd(b,a%b):a;}

int main(){
    FIO;
    cin>>t;
    while(t--){
        cin>>a>>b;
        while(a!=1){
            ll tmp = (b%a!=0) ? b/a+1:b/a;
            a = a*tmp-b; b *= tmp;
            ll res = gcd(a,b); a/=res; b/=res;
        }
        cout<<b<<"\n";
    }
    return 0;
}

결과