쉬운 수열 문제

현재 $(A_N,A_{N+1})=(P,Q)$라고 하자. $P<Q$이면 $N$의 마지막 이진 비트는 $0$이고 이전 쌍은 $(P,Q-P)$이다. $P>Q$이면 마지막 비트는 $1$이고 이전 쌍은 $(P-Q,Q)$이다.

한 번씩 빼면 값이 매우 큰 경우 느리다. $P<Q$일 때 $t=\left\lfloor\frac{Q-1}{P}\right\rfloor$만큼 한 번에 빼면 뒤의 $0$ 비트 $t$개를 제거한 것과 같다. $P>Q$도 대칭적으로 처리한다. 서로소이므로 과정은 $(1,1)$에서 끝난다.

제거한 비트 구간을 역순으로 붙인다. 현재 값이 $X$일 때 $0$을 $t$개 붙이면 $X2^t$, $1$을 $t$개 붙이면 $X2^t+(2^t-1)$이 된다. 모든 연산은 $998\,244\,353$으로 나눈 나머지로 계산한다. 유클리드 알고리즘과 같은 횟수의 단계만 필요하므로 시간 복잡도는 $O(\log \max(P,Q))$이다. Solution written by GPT5.6