UVa 701 The Archeologist‘s Dilemma

题目描述

考古学家发现一些墙壁上的数字链，左侧数字总是完整的，右侧部分常因侵蚀而缺失。她注意到所有完整数字都是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。

输入格式

输入包含若干行，每行一个正整数NNN（N≤2147483648N \le 2147483648N≤2147483648）。输入直到文件结束。

输出格式

对于每个NNN，输出一行，包含最小的正整数指数EEE，使得2E2^E2E的前缀为NNN且满足上述位数条件；若不存在，则输出no power of 2。

样例输入

1 2 10

样例输出

7 8 20

题目分析

设NNN的十进制位数为kkk，即10k−1≤N<10k10^{k-1} \le N < 10^k10k−1≤N<10k。若2E2^E2E的前缀为NNN，则存在一个整数ddd（ddd为2E2^E2E的总位数）使得

N×10d−k≤2E<(N+1)×10d−k. N \times 10^{d-k} \le 2^E < (N+1) \times 10^{d-k}.N×10d−k≤2E<(N+1)×10d−k.

这里d−kd-kd−k表示NNN后面缺失的数字位数，记为mmm。题目要求可见位数kkk严格小于缺失位数mmm，即m≥k+1m \ge k+1m≥k+1。因此我们需要寻找最小的EEE，使得存在整数m≥k+1m \ge k+1m≥k+1满足上述不等式。

对不等式取以101010为底的对数，得到

log⁡10N+m≤Elog⁡102<log⁡10(N+1)+m. \log_{10} N + m \le E \log_{10} 2 < \log_{10} (N+1) + m.log10​N+m≤Elog10​2<log10​(N+1)+m.

令L=log⁡10N+mlog⁡102L = \dfrac{\log_{10} N + m}{\log_{10} 2}L=log10​2log10​N+m​，R=log⁡10(N+1)+mlog⁡102R = \dfrac{\log_{10} (N+1) + m}{\log_{10} 2}R=log10​2log10​(N+1)+m​，则问题等价于判断区间(L,R](L, R](L,R]（左闭右开）内是否存在整数EEE。由于log⁡102\log_{10} 2log10​2为无理数，区间长度通常小于111，因此最多只有一个整数。若存在，则最小的EEE即为该整数，可以通过计算⌊R⌋\lfloor R \rfloor⌊R⌋得到（当⌊R⌋>⌊L⌋\lfloor R \rfloor > \lfloor L \rfloor⌊R⌋>⌊L⌋时）。

解题思路

采用枚举缺失位数mmm的方法。从m=k+1m = k+1m=k+1开始，依次递增mmm，对每个mmm计算：

down=⌊log⁡10N+mlog⁡102⌋, \text{down} = \left\lfloor \frac{\log_{10} N + m}{\log_{10} 2} \right\rfloor,down=⌊log10​2log10​N+m​⌋,
up=⌊log⁡10(N+1)+mlog⁡102⌋. \text{up} = \left\lfloor \frac{\log_{10} (N+1) + m}{\log_{10} 2} \right\rfloor.up=⌊log10​2log10​(N+1)+m​⌋.

若up>down\text{up} > \text{down}up>down，则说明存在整数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 Archeologist's 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//// 版权所有（C）2011，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;voidfind_smallest_exponent_by_brute_force(longnumber){longlongunsignedexponent=7;string first;while(number){first.append(1,'0'+number%10);number/=10;}string result="821";while(result.rfind(first)!=(string::size_type)(result.length()-first.length())||result.length()<(2*first.length()+1)){intcarry=0;for(inti=0;i<result.length();i++){carry=2*(result[i]-'0')+carry;result[i]='0'+carry%10;carry=carry/10;}if(carry)result.append(1,'1');exponent++;}cout<<exponent<<endl;}voidfind_smallest_exponent_by_log(longnumber){intdigits=0;longoriginal=number;while(original){digits++;original/=10;}for(intk=(digits+1);;k++){longlongdown=floor((log10(number)+k)/log10(2));longlongup=floor((log10(number+1)+k)/log10(2));if(up>down){cout<<up<<endl;return;}}}intmain(){longnumber;while(cin>>number)find_smallest_exponent_by_log(number);return0;}

总结

本题的核心是将前缀匹配条件转化为对数不等式，并利用log⁡102\log_{10} 2log10​2的无理性确保解的存在性。通过枚举缺失位数，可以在常数时间判断每个候选区间是否包含整数，从而快速找到最小指数。此方法避免了高精度计算，仅需浮点运算，实现简洁高效。需要注意边界条件：当NNN为101010的幂时，N+1N+1N+1的位数可能增加，但取对数后仍有效。该解法可推广到其他底数的幂的前缀查找问题。