---

版权信息

​来源​: 自定义题目 ​题目名称​: 麦森数

---

任务总览表

任务名称	时间限制	内存限制	分数
麦森数	2 sec	1024 MB	10 points

---

题目描述

形如 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）。

---

输出格式

• 第一行：十进制高精度数 2^P - 1 的位数；
• 第 2-11 行：十进制高精度数 2^P - 1 的最后 500 位数字（每行输出 50 位，共输出 10 行，不足 500 位时高位补 0）。

不必验证 2^P - 1 与 P 是否为素数。

---

样例输入

1279

样例输出

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

---

提示

• 使用 高精度数 来表示 ​2^P - 1​，由于该数的位数非常大，标准的整型数据类型无法表示。
• 输出时，必须按照指定的格式输出最后 500 位数字。

---

题目分析

目标

• 给定一个 P 值，计算 2^P - 1 的位数，并输出最后 500 位数字。

思路

• ​高精度计算​：由于 2^P - 1 的值非常大，无法使用普通的整数类型表示，需要使用 大数库 或 自定义高精度计算方法 来处理。
• ​位数计算​：可以通过 log10 来计算数字的位数。
• ​最后 500 位​：通过计算 2^P 的值，然后提取其最后 500 位数字。

解法

1. ​高精度计算​：使用 Python 的 int 类型（Python 自带支持任意精度整数），或使用其他编程语言中的大数库。
2. ​计算位数​：通过 log10(2^P - 1) 计算位数。
3. ​获取最后 500 位​：使用字符串处理的方法，提取最后 500 位数字并格式化输出。

---

时间复杂度分析

• 计算 2^P 的时间复杂度为 ​**O(P)**​，这主要是由于指数运算和大数计算的复杂度。
• 提取最后 500 位 和 计算位数 的操作复杂度为 ​**O(log(2^P))​，即 ​O(P)**​。

因此，整体的时间复杂度是 ​**O(P)**​，这对于 P ≤ 3100000 是可接受的。

---

结论

通过高精度计算和字符串处理，我们能够在给定时间内有效计算 2^P - 1 的位数和最后 500 位数字。