D - Takahashi变异

分数： $400$ 分

题目描述

伊芙兰喜欢养宠物游戏。

伊芙兰的宠物是Takahashi。最初，Takahashi的STR和EXP分别为$X$和$0$。 以下两种训练方式可以增加这些参数：

• 去“Kakomon Gym”：STR乘以$A$，EXP加$1$。
• 去“AtCoder Gym”：STR加$B$，EXP加$1$。

当Takahashi的STR大于等于$Y$时，他会进化，但伊芙兰认为这让他变得不那么可爱。

找到当Takahashi在不让他进化的情况下进行训练时，他的最大EXP。

约束

• $1 \leq X < Y \leq 10^{18}$
• $2 \leq A \leq 10^9$
• $1 \leq B \leq 10^9$
• 输入的所有值都是整数。

输入

从标准输入中输入数据，格式如下：

$X$ $Y$ $A$ $B$

输出

输出在给定情况下，Takahashi的最大EXP。

4 20 2 10

2

最初，Takahashi的STR为$4$。我们可以通过以下训练使他的EXP达到$2$：

• 首先，去“Kakomon Gym”训练，将他的STR变为$8$，EXP为$1$。
• 然后，去“AtCoder Gym”训练，将他的STR变为$18$，EXP为$2$。

另一方面，没有办法训练他的EXP大于$2$。

1 1000000000000000000 10 1000000000

1000000007

注意溢出问题。