D. 헨리

문제에서 주어진 방법대로, 분수 $\frac{a}{b} (a < b)$ 를 단위 분수의 합으로 나타냈을 때 마지막 단위 분수의 분모를 구하는 문제다.

문제 입력 형식의 마지막 조건에 따라 $\frac{a}{b}$ 를 구성하는 단위 분수는 31개 미만이다. 이제 문제에서 중요한 것은 $\frac{a}{b} \geq \frac{1}{x}$ 를 만족하는 최소 x 를 구하는 것이다. 이분 검색을 통해서 구해도 되고, 직접 계산을 통해 구해도 된다. 매번 이를 계산하면서 마지막 분수를 구하면 된다.

#include <stdio.h> typedef long long lld; int T; lld gcd(lld a,lld b){ return b?gcd(b,a%b):a; } struct Z{ Z(lld p,lld q){ lld g = gcd(p,q); a = p/g, b = q/g; } lld a,b; }; int main() { int a,b; for (scanf("%d",&T);T--;){ scanf("%d%d",&a,&b); Z z(a,b); while (z.a > 1){ lld n = (z.b-1)/z.a+1; z = Z(z.a*n-z.b,z.b*n); } printf("%lld\n",z.b); } }