Autor da análise: 
ctgPi
Resumo
Dado $1 \leq N \leq 2^{31}$ inteiro com $D$ dígitos, encontre o menor $E$ tal que:
- $2^E$ tem pelo menos $2D+1$ dígitos;
- os $D$ primeiros dígitos da representação decimal de $2^E$ são iguais a $N$.
Por exemplo, para $N = 10$ a resposta é $E = 20$, já que $2^E = \textbf{10}48576$. Note que $E = 10$ não é uma solução válida, já que $2^E = \textbf{10}24$ tem apenas 4 dígitos, quando o mínimo necessário é 5.
Solução
Em primeiro lugar, nós reduzimos a dimensão dos números do problema trabalhando com logaritmos:
(1)Como $N$ é inteiro, tomar os três lados da desigualdade módulo 1 preserva as desigualdades; definindo $\{x\} = x - \left\lfloor x \right\rfloor$, a desigualdade acima é quievalente a
(2)O primeiro cuidado que devemos ter é com a precisão dos números envolvidos: para $N = 2^{31}$, a largura do intervalo acima é $2.02 \times 10^{-10} \approx 2^{-32.2}$; escolhendo um valor de $E$ aleatório, essa é a probabilidade de que ele seja a solução do problema, pelo Teorema de Kronecker. Logo, devemos esperar que para valores de $N$ nesta faixa, a resposta seja da ordem de $\left( 2.02 \times 10^{-10} \right)^{-1} \approx 4.94 \times 10^9 \approx 2^{32.2}$, com um desvio padrão muito parecido (supondo uma distribuição geométrica para as respostas do problema).
Mesmo com precisão de long double (i.e. 64 bits), o erro de representação de $\log_{10} 2$ é $2^{-65}$; quando multiplicado por $E$, esse erro aumenta para $2^{-32.8}$, que é apenas $2^{-0.6} \approx 0.75$ vezes a largura do intervalo no pior caso. Portanto, é crucial fazermos todos os esforços possíveis para manter bits de precisão durante a conta.
Um fato que ajuda é que temos um tipo de inteiro com 64 bits de precisão: uint64_t. Podemos, por exemplo, implementar a seguinte função para calcular a parte fracionária de $\log_{10} x$:
uint64_t log_10(uint64_t N) { long double n = N, p = 1.0; while ((10.0 * p) >= n) p *= 10.0; return (uint64_t)(log10l(n / p) * 0x1.0p+64); }
Note que nós não fizemos while (n >= 10.0) n /= 10.0; para evitar erros de precisão: as únicas duas operações inexatas na função acima são a divisão e o log10l da última linha. Fazer a conta com uint64_t ao invés de diretamente com long doubles tem uma vantagem fundamental: o overflow de uint64_t é equivalente a tirar a parte fracionária, sem perder precisão, como ocorreria se fizéssemos a conta com long doubles; a parte inteira dos logaritmos ocuparia um ou dois bits, que seriam perdidos na mantissa do número resultante.
Munido de log_10, poderíamos simplesmente testar todos os valores possíveis de $E$, em ordem, até encontrar um que estivesse no intervalo desejado: isso leva tempo $\Theta(E)$, que como mencionado acima, pode ser muito grande.
Uma alternativa é o algoritmo baby-step giant-step: escolha um $m$ qualquer — a escolha ótima do valor de $m$ será discutida logo em breve. Pelo algoritmo de divisão euclideana, $E = mq + r$, onde $0 \leq r < m$. Calcule todos os produtos $r \log_{10} 2$ com $r$ nesse intervalo, e guarde os valores obtidos em alguma estrutura de dados que permita buscar o primeiro elemento $\geq x$ em $\Theta\left(\log m\right)$ (e.g. um vetor ordenado).
Depois, testamos todos os valores de $q$ em ordem: é fácil ver que
(3)e que, portanto, fixado um valor de $q$, basta verificar se algum dos $m$ valores de $\{r \log_{10} 2\}$ está dentro do intervalo $\left[\{\log_{10} N - q (m \log_{10} 2)\}, \{\log_{10} (N+1) - q (m \log_{10} 2)\}\right[$ (tomando cuidado com a possibilidade de que $\{\log_{10} (N+1) - q (m \log_{10} 2)\} < \{\log_{10} N - q (m \log_{10} 2)\}$, apesar de que neste caso podemos simplesmente tomar $r = 0$). Cada verificação custa $\Theta\left(\log m\right)$.
Qual é a complexidade deste algoritmo? Pré-calcular e ordenar os $\{r \log_{10} 2\}$ custa $\Theta\left(m \log m\right)$; testar todos os valores de $q$ até encontrar o valor certo custa $\Theta\left(\frac{E}{m} \log m\right)$, para um custo total de $\Theta\left(\left(m + \frac{E}{m}\right) \log m\right)$. O valor mínimo da complexidade é atingido quando $m \sim \sqrt{E}$, para um custo de $\tilde{\Theta}\left(\sqrt{E}\right)$.
Calcular $m \log_{10} 2$ é mais complicado do que parece: se escolhermos, e.g. $m = 2^{18}$, e fizermos a conta primeiro calculando o logaritmo e depois multiplicando por $m$ perdemos 18 bits de precisão. A abordagem correta é elevar 2 ao quadrado 18 vezes, dividindo por uma potência de 10 apropriada sempre que o valor se tornar muito grande:
uint64_t log_10_2_2(size_t E) { long double x = 2.0; size_t i; for (i = 0; i < E; i++) { x *= x; if (x >= exp10l(8)) x /= exp10l(8); } if (x >= exp10l(4)) x /= exp10l(4); if (x >= exp10l(2)) x /= exp10l(2); if (x >= exp10l(1)) x /= exp10l(1); return (uint64_t)(log10l(x) * 0x1.0p+64); }
Finalmente, falta a restrição do número de dígitos, mas essa é a mais simples de todas: um inteiro $k$ tem $\left\lfloor \log_{10} k \right\rfloor + 1$ dígitos; logo devemos ter
(4)Como o lado direito da última desigualdade é inteiro, o piso do lado esquerdo é redundante, e portanto é necessário e suficiente que
(5)Testes
Entrada
1
2
3
4
5
6
7
8
9
9
99
999
9999
99999
999999
9999999
99999999
999999999
1
10
100
1000
10000
100000
1000000
10000000
100000000
1000000000
1
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
2147483648
Saída
7
8
15
12
9
16
46
13
53
53
93
2621
13301
254370
5781869
38267831
146964308
1923400330
7
20
196
2136
15437
70777
325147
6432163
198096465
15042141867
7
8
12
13
14
15
109
203
689
1660
2146
2147
2148
15450
28752
70792
70793
70794
325165
325166
325167
325168
6432185
6432186
6432187
51132182
51132183
198096492
888218039
1578339586
18888942557
51586748168
Discuta o problema