2078번: 무한이진트리

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

$O(\lg(min(a,b)))$

나머지 연산을 이용해 빠르게 구한다.

#include<cstdio> 
int a, b, l, r;
int main() {
    scanf("%d%d", &a, &b);
    while (a^b) {
        l += (a - 1) / b;
        a = (a - 1) % b + 1;
        r += (b - 1) / a;
        b = (b - 1) % a + 1;
    }
    printf("%d %d", l, r);
    return 0;
}