BOJ-10253 헨리

접근

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

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

• $\frac{1}{x^{1}} \leq \frac{a}{b}$ 을 만족하는 최대의 $x^1$은 b와 a의 값은 알고있으므로 $x^1$에 2부터 값을 대입하여 쭉 올라가면 정답을 찾을 수 있을 것이다. 하지만 이는 시간초과를 받게된다.

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

• 식을 정리하여 $b/a \leq x^1$이렇게 나타내면 $O(1)$ 만에 $x^1$을 알 수 있고, a가 b의 배수가 아닌경우를 고려하여 값에 +1을 해주어야한다.

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

• $\frac{5}{7} = \frac{1}{2} +\frac{?}{?}$라는 식을 구하고 통분을 하면 $\frac{a \cdot x^1+b}{b \cdot x^1}$라는 식을 얻을 수 있고, $a=a \cdot x^1+b$, $b=b \cdot x^1$을 대입하여 과정을 반복한다.

• 이때 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;
}

결과