2^20【牛客tracker 每日一题】
2^20
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
我似乎曾记忆化搜寻过这个地方……
长途是A C M ACMACM大陆一只快乐的小男孩。今天，他在c f cfcf战场上历练，遭遇了T TT波丧尸
长途快被丧尸咬死啦！幸好他手中的两把武器都还有20 20 20 20 20^{{20}^{{20}^{20}}}20202020枚子弹，一枚子弹可以击中一个丧尸
- 武器1——【AC】：每次射击可以发射一枚子弹
- 武器2——【AK-47】：每次射击可以同时朝当前每个丧尸均发射一枚子弹
然而，丧尸有种特殊的能力，每次击中并不会死掉，反而会立刻复制出一个新的丧尸
长途有点绝望。幸好他发现当前这波的所有丧尸都处在一个特殊的圆盘上！这个圆盘被称为圆神，当丧尸的数量是2 20 2^{20}220的倍数时，可以选择启动这个装置，消灭当前这波的全部丧尸！！！
值得注意的是，一共有T TT大波丧尸，只有当一波的丧尸被全部消灭后，下一波的丧尸才会出现，并且手中武器的子弹数也会恢复
情况很紧急，长途请你帮帮他。对于每一波丧尸，最少需要射击多少次才能消灭这一波的所有丧尸。若消耗完所有的子弹都无法消灭这一波的所有丧尸，请输出− 1 −1−1
输入描述：
第一行包含一个整数T TT，表示长途遭遇了T ( 1 ≤ T ≤ 10 5 ) T (1≤T≤10^5)T(1≤T≤105)波丧尸
对于每波丧尸：
仅输入一行，包含一个正整数n ( 1 ≤ n ≤ 10 9 ) n (1≤n≤10^9)n(1≤n≤109)，表示当前这波的丧尸数
输出描述：
对于每波丧尸：
仅输出一行，若消耗完所有的子弹都无法消灭这一波的所有丧尸，输出− 1 −1−1；否则输出消灭当前这波的所有丧尸所需要的最少射击次数
示例1
输入：
3 1048575 1048576 1输出：
1 0 20解题思路
本题本质是模意义下的最少操作次数问题。每次操作可以令当前丧尸数n nn加1 11（武器1）或乘2 22（武器2），求使n nn变为2 20 2^{20}220倍数所需的最少操作次数。
1. 问题等价转化
- 目标条件：n ≡ 0 ( m o d 2 20 ) n \equiv 0 \pmod{2^{20}}n≡0(mod220)。
- 操作：
- 操作1（AC）：n → n + 1 n \to n+1n→n+1，消耗一次射击。
- 操作2（AK-47）：n → 2 n n \to 2nn→2n，消耗一次射击。
- 子弹限制：两把武器的子弹数均为天文数字20 20 20 20 20^{20^{20^{20}}}20202020，远大于任何可行操作所需，因此本题中子弹不会耗尽，始终有解。
- 最优化目标：求从初始n nn到达目标的最少操作次数。
由于目标只依赖n m o d 2 20 n \bmod 2^{20}nmod220，可先将n nn对M = 2 20 M = 2^{20}M=220取模。若余数为0 00则无需操作。否则，问题变为：在模M MM意义下，从x = n m o d M x = n \bmod Mx=nmodM出发，每次可+ 1 +1+1或× 2 \times 2×2，求变为0 00的最小步数。
2. 算法实现：枚举加法次数
观察操作性质，× 2 \times 2×2会放大之前所有+ 1 +1+1的贡献，因此最优操作序列一定将所有+ 1 +1+1放在所有× 2 \times 2×2之前（若某次+ 1 +1+1在× 2 \times 2×2之后，将其移至× 2 \times 2×2之前等价于加了0.5 0.50.5，不可能更优）。
设我们做了i ii次+ 1 +1+1，得到x = n + i x = n + ix=n+i。此后再做k kk次× 2 \times 2×2，最终值为x ⋅ 2 k x \cdot 2^kx⋅2k。要使该值成为2 20 2^{20}220的倍数，只需x ⋅ 2 k x \cdot 2^kx⋅2k包含至少20 2020个因子2 22。设x xx中因子2 22的个数为c cc（即x xx能被2 c 2^c2c整除，但不能被2 c + 1 2^{c+1}2c+1整除），则需c + k ≥ 20 c + k \ge 20c+k≥20，最小k = 20 − c k = 20 - ck=20−c。总操作次数为i + ( 20 − c ) i + (20 - c)i+(20−c)。
由于直接做20 2020次× 2 \times 2×2（i = 0 , c i=0, ci=0,c为n nn的因子2 22个数，k = 20 − c k=20-ck=20−c）总步数≤ 20 \le 20≤20。因此最优解的操作次数不可能超过20 2020，枚举i ii从0 00到20 2020即可覆盖所有可能的最优解。
- 初始r e s = 20 res = 20res=20。
- 遍历i ∈ [ 0 , 20 ] i \in [0, 20]i∈[0,20]：
- 计算x = ( n m o d M ) + i x = (n \bmod M) + ix=(nmodM)+i。
- 计算c cc：反复除以2 22直到奇数，统计除的次数。
- 更新r e s = min ( r e s , i + 20 − c ) res = \min(res, i + 20 - c)res=min(res,i+20−c)。
- 输出r e s resres。
3. 复杂度分析
- 时间复杂度：对每组数据枚举O ( L ) O(L)O(L)次，L = 20 L=20L=20，总数据量T ≤ 10 5 T \le 10^5T≤105，总操作量约2 × 10 6 2 \times 10^62×106，非常快。
- 空间复杂度：O ( 1 ) O(1)O(1)。
总结
将问题转化为模2 20 2^{20}220下的最少操作次数。利用“先加后乘”的最优性质，枚举+ 1 +1+1的次数，计算所需的× 2 \times 2×2次数，取最小值。上界为20 2020保证了极低的枚举开销，能够高效处理大量数据。
代码简要说明
- 常量定义：
L=20，MD = 1<<L（1048576 10485761048576）。 - 预处理：若n m o d M D = 0 n \bmod MD = 0nmodMD=0，直接输出0 00。
- 取模：n ← n m o d M D n \gets n \bmod MDn←nmodMD，确保n ∈ [ 1 , M D − 1 ] n \in [1, MD-1]n∈[1,MD−1]。
- 枚举：
res = L，i从0 00到L LL：x = n + i；- 计算
c（x中2 22的幂次）； nd = (L - c) + i，若nd < res则更新。
- 输出：输出
res。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidS(){ll n;cin>>n;constll L=20;constll MD=1LL<<L;if(n%MD==0){cout<<0<<endl;return;}n%=MD;ll res=L;for(ll i=0;i<=L;i++){ll x=n+i;ll c=0;while(x%2==0){x/=2;c++;}ll nd=(L-c)+i;if(nd<res)res=nd;}cout<<res<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll T;cin>>T;while(T--)S();return0;}