题解：P10320 勇气（Courage）

· · 题解

由于除了第一次强化外每次都要衰变，可以想到如果初始值翻倍且第一次强化也要衰变，则对结果没有影响。具体地，令 y=2x，强化次数为 k\left(k\in\R^*\right)。

设第 k 次强化后攻击力为 f\left(k\right)=\dfrac{y^{b_k}}{2^{a_k}}=\left(\dfrac{f\left(k-1\right)}{2}\right)^2=\dfrac{y^{2b_{k-1}}}{2^{2+2a_{k-1}}}=\dfrac{y^{2^k}}{2^{2^{\left(k+1\right)}-2}}。

则题目可转化为 f\left(k\right)=\dfrac{y^{2^k}}{2^{2^{\left(k+1\right)}-2}}\ge 2^n。

由数学知识可知：

\begin{aligned} &\begin{aligned} \text{原不等式} &\implies \log_2\left(\dfrac{y^{2^k}}{2^{2^{\left(k+1\right)}-2}}\right)\ge n\\ &\implies \log_2 y^{2^k}-\log_2 2^{2^{\left(k+1\right)-2}}\ge n\\ &\implies \log_2 y^{2^k}-2^{k+1}+2\ge n\\ &\implies 2^k\log_2 y^-2^{k+1}\ge n-2\\ &\implies \log_2 y-2\ge \dfrac{n-2}{2^k}\\ &\implies \dfrac{\log_2 y-2}{n-2}\ge \dfrac{1}{2^k}\\ &\implies \dfrac{n-2}{\log_2 y-2}\le 2^k\\ &\implies k\ge\log_2\dfrac{n-2}{\log_2 y-2} \end{aligned} \\ &\begin{aligned} & \because \mathrm{ans}\in\N^*\\ & \therefore \mathrm{ans}=\lceil k\rceil\\ & \therefore \mathrm{ans}=\lceil \log_2\dfrac{n-2}{\log_2 y-2}\rceil\\ & \therefore \mathrm{ans}=\lceil \log_2\dfrac{n-2}{\log_2 2x-2}\rceil \end{aligned} \end{aligned}

代码如下：

#include<bits/stdc++.h>
using namespace std;
double n,x,y;
signed main(){
    cin>>x>>n;
    if(x==2 && n>2){cout<<"inf";return 0;}
    else if(x==2 && n==2){cout<<1;return 0;}
    else if(n==1){cout<<0;return 0;}
    cout<<static_cast<int>(ceil(log2((n-2.0)/(log2(x*2)-2))));
    return 0;  
}