题解：P11996 我是黄色恐龙大将军

· · 题解

题目要求很简单，计算所有可能的 a_n \times b_n 值的和（相同值只算一次），其中：a_n 是 2^n 的最高非零位数字，b_n 是 5^n 的最高非零位数字。

通过分析，发现 a_n \times b_n 的值只可能取 5, 6, 7, 8, 9, 10，且每个值至少被某个正整数 n 取到。举例说明：

对于 5：例如 n=9 时，2^9=512（最高位 5），5^9=1953125（最高位 1），乘积为 5 \times 1 = 5。

对于 6：例如 n=4 时，2^4=16（最高位 1），5^4=625（最高位 6），乘积为 1 \times 6 = 6。

对于 7：例如 n=7 时，2^7=128（最高位 1），5^7=78125（最高位 7），乘积为 1 \times 7 = 7。

对于 8：例如 n=2 时，2^2=4（最高位 4），5^2=25（最高位 2），乘积为 4 \times 2 = 8。

对于 9：例如 n=5 时，2^5=32（最高位 3），5^5=3125（最高位 3），乘积为 3 \times 3 = 9。

对于 10：例如 n=1 时，2^1=2（最高位 2），5^1=5（最高位 5），乘积为 2 \times 5 = 10。

以上的值覆盖了所有可能出现的乘积，且没有其他值（如小于 5 或大于 10 的值不会出现）。

接下来设 \alpha = \log_{10} 2（必定为无理数），则：

$b_n = \lfloor 10^{1 - \{n \alpha\}} \rfloor$， 其中 $\{ \cdot \}$ 表示小数部分。 因此，$c_n = a_n \times b_n = \lfloor 10^x \rfloor \times \lfloor 10^{1-x} \rfloor$，$x = \{n \alpha\} \in [0,1)$。 由于 $\alpha$ 无理，序列 $\{n \alpha\}$ 在 $[0,1)$ 上稠密。通过分析函数 $c(x)$ 的分段性质（关键点为 $x = \log_{10} k$ 和 $x = 1 - \log_{10} m$，$k,m=2,\dots,9$），可得 $c(x)$ 的值域为 $\{5, 6, 7, 8, 9, 10\}$。 所有不同值的和为： $5 + 6 + 7 + 8 + 9 + 10 = 45

综上所述，所有 a_n \times b_n 值的和为 45。（代码总会写了吧）

Q.E.D.