/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
いろはちゃんはペットを育てるゲームにはまっています。
いろはちゃんはペットとして高橋君を飼っており、はじめ高橋君の 強さ は X 、経験値 は 0 です。 これらの値は次の 2 種類の特訓によって増加します。
- カコモンジムに通う：強さが A 倍になり、経験値は 1 増える。
- AtCoderジムに通う：強さが B 増え、経験値は 1 増える。
高橋君は強さが Y 以上になると進化しますが、進化しない方がかわいいといろはちゃんは思っています。
そこで、強さが Y 以上にならないように高橋君に特訓を課すとき、経験値の最大値を求めてください。
制約
- 1 \leq X < Y \leq 10^{18}
- 2 \leq A \leq 10^9
- 1 \leq B \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
X Y A B
出力
与えられた条件の下での経験値の最大値を出力せよ。
入力例 1
4 20 2 10
出力例 1
2
最初、高橋君の強さは 4 です。次のような特訓方法によって、経験値を 2 にすることができます。
- まず カコモンジムに通うことで、高橋君の強さは 8、経験値は 1 になります。
- 次に、AtCoderジムに通うことで、高橋君の強さは 18、経験値は 2 になります。
どのような特訓方法によっても、経験値を 2 より大きくすることはできません。
入力例 2
1 1000000000000000000 10 1000000000
出力例 2
1000000007
オーバーフローに注意してください。
Score : 400 points
Problem Statement
Iroha is into a game where you keep pets.
Iroha's pet is Takahashi. Initially, Takahashi's STR and EXP are X and 0, respectively. These parameters increase in the following two kinds of training:
- Go to Kakomon Gym: the STR gets multiplied by A, and the EXP increases by 1.
- Go to AtCoder Gym: the STR increases by B, and the EXP increases by 1.
Takahashi evolves when his STR becomes Y or greater, but Iroha thinks that makes him less cute.
Find the maximum possible EXP of Takahashi when he is trained without letting him evolve.
Constraints
- 1 \leq X < Y \leq 10^{18}
- 2 \leq A \leq 10^9
- 1 \leq B \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
X Y A B
Output
Print the maximum possible EXP of Takahashi under the given situation.
Sample Input 1
4 20 2 10
Sample Output 1
2
Initially, Takahashi's STR is 4. We can make his EXP 2 in the following course of training:
- First, go to Kakomon Gym, which makes his STR 8 and his EXP 1.
- Then, go to AtCoder Gym, which makes his STR 18 and his EXP 2.
On the other hand, there is no way to train him so that his EXP becomes greater than 2.
Sample Input 2
1 1000000000000000000 10 1000000000
Sample Output 2
1000000007
Watch out for overflows.