32285번 - 시간을 달려서 (Rough)

문제

미처 말하지 못했어

다만 너를 좋아했어

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

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

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

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

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

처음에 나는 시간 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$

노트

[フレーム]

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