02706: 麦森数

快速幂，http://cs101.openjudge.cn/routine/02706/

形如2^p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2^p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。任务：从文件中输入P (1000<P<3100000) ,计算 2^p-1 的位数和最后500位数字（用十进制高精度数表示）

输入

文件中只包含一个整数P (1000<P<3100000)

输出

第1行：十进制高精度数 2^p-1 的位数。第2-11行：十进制高精度数 2^p-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）不必验证 2^p-1与P是否为素数。

样例输入

样例输出

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

来源

联赛复赛试题2003

三个参数时：pow(a, b, mod)，计算的是 (a ** b) % mod，这个三参数版本是高度优化的，内部使用了快速幂 + 模运算优化（也叫“模幂快速算法”），避免了先算出巨大的 a**b 再取模，效率极高。

python

p=int(input())
print(int(0.30102999566398114*p)+1)
r=str(pow(2,p,10**500)-1)
r='0'*(500-len(r))+r
for i in range(10):
    print(r[50*i:50*(i+1)])

python

# 23数院 胡睿诚
from math import log10, ceil
M = 10**500
MAXP = 3100000

p = int(input())
print(int(p*log10(2)) + 1)
#print(ceil(p*0.3010299956639812))

a = [2]
for _ in range(len(bin(MAXP)) - 2):
    a.append((a[-1]**2) % M)

s = 1
i = 0
for j in reversed(bin(p)[2:]):
    if j == '1':
        s = (s*a[i]) % M
    i += 1

ans = list(str(s-1))
l = len(ans)
if l < 500:
    ans = ['0']*(500-l)+ans
for i in range(0, 500, 50):
    print(''.join(ans[i:i+50]))

python

from math import log10, ceil
# 定义一个常量 M 用于取模运算，M 为 10 的 500 次方
M = 10**500
# 定义一个常量 MAXP 表示 p 的最大值
MAXP = 3100000

# 从用户输入中读取 p 的值
p = int(input())
# 计算 2^p - 1 的位数，因为 2^p - 1 的位数和 2^p 的位数相同，所以使用公式 int(p * log10(2)) + 1 计算
print(int(p*log10(2)) + 1)
# 另一种计算位数的方式，注释掉了，这里使用了近似值 0.3010299956639812 代替 log10(2)
#print(ceil(p*0.3010299956639812))

# 初始化一个列表 a，用于存储 2 的幂次取模 M 的结果，初始值为 2
a = [2]
# 循环次数为 MAXP 的二进制表示的长度减 2，因为 bin 函数返回的字符串以 '0b' 开头
for _ in range(len(bin(MAXP)) - 2):
    # 计算列表 a 中最后一个元素的平方并对 M 取模，将结果添加到列表 a 中
    a.append((a[-1]**2) % M)

# 初始化结果 s 为 1
s = 1
# 初始化索引 i 为 0
i = 0
# 反转 p 的二进制表示（去掉开头的 '0b'），并遍历每一位
for j in reversed(bin(p)[2:]):
    if j == '1':
        # 如果当前位为 1，则将 s 乘以 a[i] 并对 M 取模
        s = (s*a[i]) % M
    # 索引 i 加 1
    i += 1

# 将计算结果 s 减 1 并转换为列表
ans = list(str(s-1))
# 获取结果列表的长度
l = len(ans)
# 如果结果列表的长度小于 500，在列表前面补 0 直到长度为 500
if l < 500:
    ans = ['0']*(500-l)+ans
# 按每行 50 位输出结果
for i in range(0, 500, 50):
    print(''.join(ans[i:i+50]))

02706: 麦森数 ​

02706: 麦森数