백준 10253번 C언어 풀이

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

10253번: 헨리

인생 첫 백준 골드티어문제이다. 그냥 뭣같이 어렵다.

 

설명만 보고 소수로 접근해버리는 순간 어째서 컴퓨터는 소수도 제대로 처리를 못하는지 욕하게 되는 문제이다. 이 문제는 소수로 접근해서는 안되며, 분수의 차와 약분을 구현해서 풀어내야 한다. 

 

#include <stdio.h>

int gcd (int a, int b) { 
    /* Ucildian gcd algorithm */
    int rest = 1;
    if (a < b) {
        int temp = b;
        b = a;
        a = temp;
    }
    while(rest != 0){ 
        rest = a % b; 
        a = b; // a -> b
        b = rest; // b -> r1
    }
    return a;
}

int main () {
    int T, a, b, x, temp;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &a, &b);

        while (a != 1) {
            x = b/a + 1;
            a = a*x - b;
            b *= x;
            temp = gcd(a, b);
            a /= temp;
            b /= temp;
        }
        printf("%d\n", b);
    }
    return 0;
}