686 Powers of Two

Problem 686

$2^7=128$ 是第一个以 12 开头的 2 的幂次数。下一个是 $2^{80}$。

$p(L,n)$ 表示满足 $2^j$ 以 $L$ 开头的第 $n$ 个 $j$ 的值。所以 $p(12,1)=7$，$p(12,2)=80$。

题中给出 $p(123,45)=12710$ 以验证程序。

求 $p(123,678910)$。

$2^{12710}$ 就是一个比较大的数字，如果使用 BigInteger.ToString 检查其是否以 123 开头还好，但是这才第 45 个以 123 开头的幂次，第 678910 个满足条件的幂次要大的多得多，时间也要长太多，所以我们需要一个速度更快的方式来检查。

对这个数字进行简单的处理： $$2^j=10^d=10^{\lfloor d \rfloor}\times 10^{d-\lfloor d \rfloor}$$ 而后者就是我们想要的了，整数部分是第一个数字，小数点后面分别是第二个数字和第三个数字。

double Log102 = Math.Log10(2);
var d = j * Log102;
var rem = d - (int)d;

var leading = Math.Pow(10, rem);
int num = (int)(leading * 100);

如果 num == 123 的话，就说明它满足条件。我依次遍历 $j$，大概需要 10 秒时间找到第 678910 个，也就是题目想要的答案。

怎么优化呢？

我打印了前面几十个满足条件的$j$，然后做差得到一个数列，我发现差值只可能是 196，289 和 485，并且 289 后面只能是 196，196 后面只能是其他两数，485 后面不会是 289。按照这个思路优化，只要不到 100ms 就能得到结果，因为省去了上百倍的候选值 $j$。

为什么只能是这三个数呢？因为它们的 $d$ 值非常的接近整数。

>>> import math
>>> math.log(2) / math.log(10) * 196
59.001879150140304
>>> math.log(2) / math.log(10) * 289
86.99766874689055
>>> math.log(2) / math.log(10) * 485
145.99954789703085