[NOIP 2003 普及组] 麦森数

· · 题解

一篇 python 题解。

先看第一问。一个数 x 的位数，相当于 \log_{10} x + 1。用我们小学二年级就学过的换底公式，可以得到：

\log_{10} 2^{P} + 1 = \dfrac{\log_{2} 2^P}{\log_{2} 10}+1=\dfrac{P}{\log_{2}10}+1

再看第二问，要我们求出 2^P \bmod 10^{500} 的值。python 中的 pow 函数还可以接受一个参数，表示结果对其取模。pow 函数内部使用快速幂实现，速度非常快，同时其边算边取模避免浪费大量时间。

手写高精题，一边玩去。

from math import log2

n = int(input())
print(int(n / log2(10)) + 1)
P = pow(10, 500)
x = pow(2, n, P)
x = (x - 1) % P
s = str(x)
s = '0' * (500 - len(s)) + s
for i in range(10):
    for j in range(50):
        print(s[i * 50 + j], end="")
    print()