각 자리 합의 두 배

시간 제한2초메모리 제한1024 MB

요약

N과 X가 주어졌을 때, 각 항이 이전 항의 자릿수 합의 두 배인 수열에서 첫 항이 X인 N번째 항을 구합니다.

난이도: 보통10점 중 4점
유형: 시뮬레이션, 수학, 해시맵
정답자: 아직 제출이 없습니다

문제

바이타자르는 자연수 수열을 만든다. 첫 항은 그가 좋아하는 수 X이며, $A_1 = X$ 이다. 이후 각 항은 바로 앞 항의 각 자리 숫자의 합을 두 배 한 값이다. 즉 모든 $i \ge 1$ 에 대해 $A_{i+1} = 2s(A_i)$ 가 성립하고, 여기서 $s(k)$ 는 $k$ 의 각 자리 숫자의 합이다. 예를 들어 X = 1이면 처음 항들은 $A_1 = 1$ , $A_2 = 2$ , $A_3 = 4$ , $A_4 = 8$ , $A_5 = 16$ , $A_6 = 14$ 순서로 이어진다. N번째 항을 빠르게 구할 수 있는가? N과 X를 입력받아 X에서 시작하는 바이타자르의 수열에서 N번째 항을 출력하는 프로그램을 작성하라.

입력

첫 줄에 자연수 N과 X가 주어진다 ( $1 \le N, X \le 10^{18}$ ).

출력

바이타자르 수열의 N번째 항 $A_N$ 을 정수 하나로 출력한다.

예제2

예제 1
입력
```
6 1
```
예상 출력
```
14
```
예제 2
입력
```
4 9912
```
예상 출력
```
6
```