自动搬运

查看原文

来自洛谷，原作者为

	NaCly_Fish 北海虽赊，扶摇可接。

搬运于2025-08-24 22:56:53，当前版本为作者最后更新于2024-04-05 22:38:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个比较直观的想法，就是先求出 $k$ 次技能后的攻击力 $a_k$ 为多少，可以列出：

$$x \ , \ x^2 \ , \ \frac{x^4}{2^2} \ , \ \frac{x^8}{2^6} \ , \ \frac{x^{16}}{2^{14}} \ , \ \cdots $$

简单找一下规律，就可以发现对于 $k\geq 1$：

$$a_k=\frac{x^{2^k}}{2^{2^k-2}}$$

使用归纳法，根据 $a_k= (a_{k-1}/2)^2$ 就可以证明这个结论。首先如果 $x\geq 2^n$ 答案直接就是零，如果 $x=2$ 而 $n>2$ 则无解。

对于一般的情况，需要找出最小的正整数 $k$ 使得

$$\frac{x^{2^k}}{2^{2^k-2}}\geq 2^n$$

只要学过一些高中数学的内容，我们就知道此不等式可以用对数来解决，即转化为：

$$\begin{aligned}2^k\log_2x-(2^k-2) &\geq n \\ 2^k &\geq \frac{n-2}{\log_2x -1}\end{aligned} $$

可以直接从小到大枚举 $k$ 来判断，也可以对右式再计算 $\log_2$，向上取整即是答案。