题解：P10320 勇气（Courage）

· · 题解

一个比较直观的想法，就是先求出 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，向上取整即是答案。