P3922

jijidawang · 2022-06-14 15:32:27 · 题解

题目背景好评

一个数乘 2 时，最高位的变化有下面几种：

其中要想最高位为 4 必须经过 4 次操作回到 1，所以要有 4 的概率为 \lg(5/4)=\lg(1.25) .

于是答案就是 \lceil k\lg(1.25)\rceil .

然而这个真正的 k 可以达到 10^{233}，所以我们需要一个高精 .

高精浮点数我又不会写，只能用 Python 了 .

Python 有一个库叫 decimal，里面自带一个高精浮点数 Decimal，可以通过 getcontext().prec 调精度 .

具体看代码吧：

from decimal import Decimal, getcontext
getcontext().prec = 1000
n, k0 = input().split()
n = Decimal(n)
k0 = Decimal(k0)
if n == Decimal('0'):
    k0 = 10 ** k0
print((k0 * Decimal('1.25').log10() + Decimal('0.999999999')) // Decimal('1'))

要注意的是运算要把一般字面量强转成 Decimal .

这个代码可能写法比较丑，仅供参考 .

听说标程写了 17k