[10253] 헨리

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

 처음에 i = 2에서 카운트를 올려가며 a/b >= 1/x를 만족하는 가장 큰 분수 1/x를 찾았는데 시간초과가 떴다.

아래 방법으로 풀고나서도 최대공약수 구하는 함수를 i = b로 두고 i를 줄이면서 a와 b에 나누는 식으로 함수를 짰더니

또 시간초과가 떠서 시간초과 비율만 높였다.

a/b >= 1/x를 만족하는 가장 큰 분수 1/x를 찾는게 관건이다.

a/b >= 1/x식은 다음과 같이 변경 가능하다.

이때 마지막 식을,

 x = b / a +1

과 같이 표현할 수 있는데, 이는 b와 a모두 int형이라 나누기 연산을 통해 x보다 1작은 수를 얻을 수 있기 때문이다.

이렇게 x를 구한 후 다음 x를 구하기 위해 다음 a/b를 다음과 같이 구한다.

a = a * x -b

b = b * x

만약 a와b에 최대공약수가 존재한다면 최대공약수를 나눠서 기약분수로 만든후,

a == 1 일때까지  다음x를 구하는 과정을 반복한다.

---

#include <cstdio>

using namespace std;

int Gcd(int a,int b){

return b == 0 ? a : Gcd(b,a%b);

}

int main(){

int T = 0;

int a = 0, b = 0, x = 0, g = 0;

scanf("%d",&T);

for(int k = 0;k<T;k++){

scanf("%d %d",&a,&b);

while(a != 1){

x = b / a +1;

a = a * x - b;

b = b * x;

g = Gcd(a,b);

a /= g;

b /= g;

}

printf("%d\n",b);

}

return 0;

}