做不来小学数学题了。

题目链接

题意：求$2^0, 2^1, 2^2, 2^3, \dots , 2^k$中一共有多少个数最高位为$4$。（$k \leqslant 10^{233}$)

我们有一个数$x=1$，每次操作要把$x$乘$2$。重复$k$次。然后我们就是要求有多少次操作结束后$x$的最高位为$4$。

进行一次操作后，如果$x$的位数加了$1$，那么$x$的最高位必定为$1$，否则$x$的最高位就会$\times 2$或$\times 2 +1 $。假设当前$x$的最高位为$1$，设再进行$i$次操作后$x$的位数恰好加了一。显然$i=3$或$4$。在这个过程中可能的最高位变化序列不多，枚举一下发现如果$i=3$，那么最高位变化序列中一定没有$4$，否则一定有$4$。

我们先假设$2^k$的最高位为$1$（如果不是，我们把最后一段操作的贡献单独计算一下）。那么我们就是要求：有多少次，我们使用了四次操作使得$x$的位数恰好加了$1$。设答案为$y$，如果$2^k$一共有$b$位，我们就是需要解方程$4y + 3(b-1-y) = k$。那么$y=k + 3 - 3b$。对于求$b$的值，容易发现$b = \lfloor log_{10}{2^k} \rfloor + 1 = \lfloor k \log_{10}2 \rfloor + 1$。

对于高精度部分：当然是使用$\text{python}$辣！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
from decimal import Decimal
from decimal import getcontext
getcontext().prec = 1000

def getdig(n):
	return int(Decimal('2').log10() * n)

t, n=map(int, input().split())
if t == 0:
	n = 10 ** n

d = getdig(n)
cnt = 0

for i in range(n, -1, -1):
	if getdig(i) == d:
		cnt += 1
		nn = i
	else:
		break
print(nn - 3 * d + (cnt == 4 or (cnt == 3 and getdig(n + 1) == d)))