시간복잡도 $O(L + NlogL), L = log(max(S_0, S_1))$ 풀이 1번째 test case인 (21, 12)를 관찰해보자. 21, 12, 9, 3, 6, 3, 3, 0, 3, 3, 0, ... 보이는 것과 같이 3, 3, 0이 반복됨을 관측할 수 있다. 이로부터 같은 수가 연속해서 나오면 그 뒤는 $a, a, 0$이 반복됨을 알 수 있다. 그러나 $(10^{18}, 1)$와 같은 경우 같은 수가 연속한 경우까지 너무 오래 걸린다. 만약 $(a, b)$에서 $a \gg b$라면, $a, b, a-b, a-2b, b$까지는 자명함을 알 수 있다. 즉 $(a, b)$에서 $(a-2b, b)$, 나아가 $(a-2kb, b)$까지 확장시킬 수 있는 것이다. 정리해보자면, $(a, b)$에서 i..
