Takahashi Unevolved

题目描述

Iroha 喜欢玩养宠物的游戏。 Iroha 的宠物是 Takahashi。最初，Takahashi 的 STR 和 EXP 分别是 $X$ 和 $0$。 这些参数通过以下两种训练方式增加：

去 Kakomon Gym：STR 会乘以 $A$，EXP 增加 $1$。 去 AtCoder Gym：STR 会增加 $B$，EXP 增加 $1$。

当 STR 变为 $Y$ 或更大时 Takahashi 会进化，但 Iroha 认为那样会让他变得不那么可爱。 求在不让他进化的情况下，Takahashi 可达到的最大 EXP。

输入格式

输入来自标准输入，格式如下： $X$ $Y$ $A$ $B$

输出格式

输出在给定条件下 Takahashi 的最大可能 EXP。

4 20 2 10

2

1 1000000000000000000 10 1000000000

1000000007

提示

1 \leq X < Y \leq 10^{18} $2 \leq A \leq 10^9$ $1 \leq B \leq 10^9$ 输入中的所有值均为整数。最初，Takahashi 的 STR 为 $4$。我们可以通过以下训练使他的 EXP 达到 $2$：

首先，去 Kakomon Gym，使 STR 变为 $8$，EXP 为 $1$。 然后，去 AtCoder Gym，使 STR 变为 $18$，EXP 为 $2$。

另一方面，没有办法使他的 EXP 超过 $2$。
注意溢出。

标签: AtCoder|abc180D

来源

AtCoder|abc180D