题目描述考古学家发现一些墙壁上的数字链左侧数字总是完整的右侧部分常因侵蚀而缺失。她注意到所有完整数字都是222的幂因此需要验证这一假设。给定一个正整数NNN要求找到最小的正整数指数EEE使得2E2^E2E的十进制表示的前若干位恰好等于NNN并且已知可见位数严格小于缺失位数即2E2^E2E的总位数至少为2×len(N)12 \times \text{len}(N) 12×len(N)1。若不存在这样的EEE则输出no power of 2。输入格式输入包含若干行每行一个正整数NNNN≤2147483648N \le 2147483648N≤2147483648。输入直到文件结束。输出格式对于每个NNN输出一行包含最小的正整数指数EEE使得2E2^E2E的前缀为NNN且满足上述位数条件若不存在则输出no power of 2。样例输入1 2 10样例输出7 8 20题目分析设NNN的十进制位数为kkk即10k−1≤N10k10^{k-1} \le N 10^k10k−1≤N10k。若2E2^E2E的前缀为NNN则存在一个整数dddddd为2E2^E2E的总位数使得N×10d−k≤2E(N1)×10d−k. N \times 10^{d-k} \le 2^E (N1) \times 10^{d-k}.N×10d−k≤2E(N1)×10d−k.这里d−kd-kd−k表示NNN后面缺失的数字位数记为mmm。题目要求可见位数kkk严格小于缺失位数mmm即m≥k1m \ge k1m≥k1。因此我们需要寻找最小的EEE使得存在整数m≥k1m \ge k1m≥k1满足上述不等式。对不等式取以101010为底的对数得到log10Nm≤Elog102log10(N1)m. \log_{10} N m \le E \log_{10} 2 \log_{10} (N1) m.log10Nm≤Elog102log10(N1)m.令Llog10Nmlog102L \dfrac{\log_{10} N m}{\log_{10} 2}Llog102log10NmRlog10(N1)mlog102R \dfrac{\log_{10} (N1) m}{\log_{10} 2}Rlog102log10(N1)m则问题等价于判断区间(L,R](L, R](L,R]左闭右开内是否存在整数EEE。由于log102\log_{10} 2log102为无理数区间长度通常小于111因此最多只有一个整数。若存在则最小的EEE即为该整数可以通过计算⌊R⌋\lfloor R \rfloor⌊R⌋得到当⌊R⌋⌊L⌋\lfloor R \rfloor \lfloor L \rfloor⌊R⌋⌊L⌋时。解题思路采用枚举缺失位数mmm的方法。从mk1m k1mk1开始依次递增mmm对每个mmm计算down⌊log10Nmlog102⌋, \text{down} \left\lfloor \frac{\log_{10} N m}{\log_{10} 2} \right\rfloor,down⌊log102log10Nm⌋,up⌊log10(N1)mlog102⌋. \text{up} \left\lfloor \frac{\log_{10} (N1) m}{\log_{10} 2} \right\rfloor.up⌊log102log10(N1)m⌋.若updown\text{up} \text{down}updown则说明存在整数EEE且最小的EEE即为up\text{up}up因为区间内至多一个整数且up\text{up}up是满足上界条件的最小整数。输出该EEE并结束当前NNN的搜索。由于对于任意正整数NNN总存在无穷多个222的幂以前缀NNN开头且mmm可以任意大因此搜索必然在有限步内终止。本题输入数据保证不会出现无解的情况但若设计程序需处理无解可设定一个较大的上界不过根据数学性质始终能找到解故无需额外处理。算法的时间复杂度为O(答案)O(\text{答案})O(答案)但实际答案不会太大通常小于10610^6106空间复杂度为O(1)O(1)O(1)。代码实现// The Archeologists Dilemma 考古学家的烦恼// PC/UVa IDs: 110503/701, Popularity: A, Success rate: low Level: 1// Verdict: Accepted// Submission Date: 2011-05-29// UVa Run Time: 0.212s//// 版权所有C2011邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;voidfind_smallest_exponent_by_brute_force(longnumber){longlongunsignedexponent7;string first;while(number){first.append(1,0number%10);number/10;}string result821;while(result.rfind(first)!(string::size_type)(result.length()-first.length())||result.length()(2*first.length()1)){intcarry0;for(inti0;iresult.length();i){carry2*(result[i]-0)carry;result[i]0carry%10;carrycarry/10;}if(carry)result.append(1,1);exponent;}coutexponentendl;}voidfind_smallest_exponent_by_log(longnumber){intdigits0;longoriginalnumber;while(original){digits;original/10;}for(intk(digits1);;k){longlongdownfloor((log10(number)k)/log10(2));longlongupfloor((log10(number1)k)/log10(2));if(updown){coutupendl;return;}}}intmain(){longnumber;while(cinnumber)find_smallest_exponent_by_log(number);return0;}总结本题的核心是将前缀匹配条件转化为对数不等式并利用log102\log_{10} 2log102的无理性确保解的存在性。通过枚举缺失位数可以在常数时间判断每个候选区间是否包含整数从而快速找到最小指数。此方法避免了高精度计算仅需浮点运算实现简洁高效。需要注意边界条件当NNN为101010的幂时N1N1N1的位数可能增加但取对数后仍有效。该解法可推广到其他底数的幂的前缀查找问题。
