스턴 수열

시간 제한1초메모리 제한512 MB

요약

기약분수 p/q가 주어질 때, 스턴의 이원 수열에서 b(k)=p이고 b(k+1)=q인 위치 k를 구해 998244353으로 나눈 나머지를 출력한다.

난이도: 어려움10점 중 8점
유형: 수학, 정수론, 분할 정복, 조합론
정답자: 아직 제출이 없습니다

문제

스턴 삼각형은 각 행의 일부 값이 윗 행 값들의 합이라는 점에서 파스칼 삼각형과 비슷하다. 다만 여기서는 윗 행의 값이 그대로 아래로 복사되기도 한다.

                                                              1                                                               
                              1                               1                               1                              
              1               1               2               1               2               1               1              
      1       1       2       1       3       2       3       1       3       2       3       1       2       1       1      
  1   1   2   1   3   2   3   1   4   3   5   2   5   3   4   1   4   3   5   2   5   3   4   1   3   2   3   1   2   1   1  
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1

행 n에는 2n - 1개의 원소 S(n, k)가 있다. 여기서

k ≤ 0 또는 k ≥ 2n이면 S(n, k) = 0
S(1, 1) = 1
n ≥ 1에 대해 S(n+1, 2*k) = S(n, k)
S(n+1, 2*k+1) = S(n, k) + S(n, k+1)

S(n+1, k)가 S(n, k) 바로 아래에 오도록 S(n, k) 값을 정렬하면 다음과 같다.

1
1 1 1
1 1 2 1 2 1 1
1 1 2 1 3 2 3 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1
1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 1 4 3 5 2 5 3 4 1 3 2 3 1 2 1 1

n이 충분히 크면 S(n+1, k) = S(n, k)임을 알 수 있다.

이 극한값들을 나열한 수열을 스턴 이원 수열이라 한다.

b(1), b(2), b(3), …

이 수열은 모든 양의 유리수 r에 대해 r = b(k)/b(k+1)을 만족하는 k가 정확히 하나 존재한다는 성질을 가진다.

예를 들어 3 / 5 = b(10) / b(11)이다.

기약분수 p/q를 입력으로 받아 p = b(k)이고 q = b(k+1)인 k를 출력하는 프로그램을 작성하라. 이 수는 매우 커질 수 있으므로 큰 소수 998,244,353으로 나눈 나머지를 출력한다.

입력

입력은 서로소인 두 십진 정수 p, q가 공백으로 구분되어 한 줄에 주어진다. (1 ≤ p, q ≤ 400000)

출력

p = b(k)이고 q = b(k+1)인 정수 k를 998,244,353으로 나눈 나머지를 한 줄에 출력한다.

예제2

예제 1
입력
```
3 5
```
예상 출력
```
10
```
예제 2
입력
```
1234 763
```
예상 출력
```
525909
```