AT_abc180_d 题解
本篇题解为此题较简单做法及较少码量，并且码风优良，请放心阅读。
题目简述
现有 \(STR\) 和 \(EXP\) 两个变量，初始化分别为 \(X\) 和 \(0\)，可对变量 \(STR\) 做以下两种操作：
-
将 \(STR\) 乘 \(A\)，并将 \(EXP\) 自加 \(1\)。
-
将 \(STR\) 加上 \(B\)，并将 \(EXP\) 自加 \(1\)。
在 \(STR < Y\) 的情况下，求 \(EXP\) 的最大值。
思路
本蒟蒻读完题目后：“贪心!”
那么贪心该怎么贪？通过题意我们很容易想到，无论是执行第一个造作还是第二个操作对 \(EXP\) 的影响不变，故就需要我们衡量操作一或二的优势。
如执行操作一比执行操作二更优，则有：
\[STR \times A < STR + B
\]
同时需满足：
\[STR \times A < Y
\]
而自信提交的我结果就可想而知了，重新看了一遍题目，发现数据范围：\(1 \le X < Y \le 10^{18}\)，\(2 \le A \le 10\)，\(1 \le B \le 10^9\)。
那么 \(STR \times A\) 就有爆 \(\text{long long}\) 的可能，通过简单的不等式移项可变化为：
\[STR < Y / A
\]
这样操作一比操作二更优的情况就解决了。又因为贪心思想，当操作二更优时可直接计算还可加多少 \(B\)，直接加到 \(ans\) 里即可，因为此时再进行操作一必定超过 \(Y\) 或 \(STR \times A \ge STR + B\)。
经过以上分析，即可得到以下代码：
#include<iostream>
using namespace std;
long long x, y, a, b, ans = 0; // 开 long long
int main() {
cin >> x >> y >> a >> b; // 输入
while(x < y) {
if(x < y / a && x * a < x + b) x *= a, ans ++; // 操作一比操作二更优，防止爆 long long 优化
else break; // 操作二更优
}
ans += (y - x - 1) / b; // 计算操作二还可执行多少次
cout << ans << endl; // 输出，换行好习惯
return 0;
}
\(\text{The End!!!}\)
提交了 \(5\) 次，我崩溃了 qwq。。