시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB604875615.686%

문제

미처 말하지 못했어

다만 너를 좋아했어

어린 날의 꿈처럼 마치 기적처럼

시간을 달려서 어른이 될 수만 있다면

거친 세상 속에서 손을 잡아줄게

나는 시간을 달려서 너를 만나고자 한다.

나와 네가 있는 세계에서 시간은 음이 아닌 정수로 나타낼 수 있다.

처음에 나는 시간 $0$에 있고, 너는 시간 $G$에 있다.

시간 $x$에 있는 내가 시간을 달려 이동할 수 있는 방법은 2가지가 있다.

  • $x+1$로 이동한다
  • $2 \times x$로 이동한다

내가 있는 시간은 이상한 구조로 되어 있기 때문에, 이동한 뒤 나의 시간이 $F$ 이상이라면 나는 $x \bmod F$ 시간으로 이동하게 된다. 여기서 $x \bmod F$란 $x$를 $F$로 나눈 나머지를 의미한다.

내가 시간 속에 갇혀 길을 헤매지 않도록, 너의 시간에 도착하기 위해 시간을 달려 이동하는 횟수의 최솟값을 구하여라.

입력

첫째 줄에 양의 정수 $G,F$가 주어진다.

출력

첫째 줄에 시간을 달려 이동하는 횟수의 최솟값을 출력하라.

제한

  • $0<G<F \leq 10^{18}$
  • $G \leq 10^7$

예제 입력 1

5 6

예제 출력 1

4

0→1→2→4→5 순서대로 이동하면 된다.

예제 입력 2

7 9

예제 출력 2

5

0→1→2→4→8→7$(16 \bmod 9)$ 순서대로 이동하면 된다.

노트

입력이 C/C++의 int 범위를 넘어갈 수 있으므로 long long 자료형을 사용하는 것을 추천한다.