https://www.acmicpc.net/problem/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;
}
'coding_test > BAEKJOON' 카테고리의 다른 글
백준 9009번 C언어 풀이 (0) | 2021.09.26 |
---|---|
백준 2798번 C언어 풀이 (0) | 2021.09.19 |
백준 9020번 C언어 풀이 (0) | 2021.09.16 |
백준 2914번 C언어 풀이 (0) | 2021.09.15 |
백준 11653번 C언어 풀이 (0) | 2021.09.14 |