[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 函数内部使用快速幂实现，速度非常快，同时其边算边取模避免浪费大量时间。

手写高精题，一边玩去。

PYTHON

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()

[NOIP 2003 普及组] 麦森数

文章操作

相关推荐

评论

[NOIP 2003 普及组] 麦森数