101803: [AtCoder]ABC180 D - Takahashi Unevolved

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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.

Input

题意翻译

### 题目描述 Iroha 正在玩一个宠物养成的游戏。 Iroha 的宠物名字叫 Takahashi。初始,Takahashi 的 **STR** 值为 $X$,**EXP** 值为 $0$。Iroha 可以带宠物到以下任意一个 Gym 进行训练: - Kakomon Gym:**STR** 值将会变为原来的 $A$ 倍,**EXP** 值将会加上 $1$。 - AtCoder Gym:**STR** 值将会加上 $B$,**EXP** 值将会加上 $1$。 当 Takahashi 的 **STR** 值大于等于 $Y$,Takahashi 会进化形态。 但是 Iroha 认为进化的 Takahashi 没那么可爱,于是 Iroha 想求出在保证 Takahashi 不进化的情况下,能达到的最大 **EXP** 值是多少。 ### 输入格式 一行四个整数,$X\ Y\ A\ B$。 ### 输出格式 一行一个表示最大 **EXP** 值的整数。 @[hellolin](/user/751017) 译

加入题单

上一题 下一题 算法标签: