【题目来源】
洛谷：[P1045 NOIP 2003 普及组] 麦森数 - 洛谷 (luogu.com.cn)
【题目描述】
形如 \(2^P-1\) 的素数称为麦森数，这时 \(P\) 一定也是个素数。但反过来不一定，即如果 \(P\) 是个素数，\(2^P-1\) 不一定也是素数。到 \(1998\) 年底，人们已找到了 \(37\) 个麦森数。最大的一个是 \(P=3021377\)，它有 $909526 $ 位。麦森数有许多重要应用，它与完全数密切相关。
任务：\(P(1000\lt P\lt 3100000)\)，计算 \(2^P-1\) 的位数和最后 \(500\) 位数字（用十进制高精度数表示）
【输入】
文件中只包含一个整数 \(P(1000\lt P\lt 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
【算法标签】
《洛谷 P1045 麦森数》 #数学# #高精度# #NOIP普及组# #2003#
【代码详解】
#include <iostream>
#include <cmath>
using namespace std;long long a[501] = {0}; // 数组a用于存储高精度计算结果，初始化为0// 计算2的n次方
long long cp(int n)
{long long result = 1;for (int i = 1; i <= n; i++) result *= 2; // 每次乘以2return result; // 返回2的n次方
}int main()
{int p; // 输入的指数pcin >> p; // 输入p// 将p分解为num1和num2，其中num1是p除以32的商，num2是余数int num1 = p / 32; // num1表示需要乘以2^32的次数int num2 = p - num1 * 32; // num2表示剩余的乘法次数（每次乘以2）long long x = cp(32); // 计算2^32的值a[500] = 1; // 初始化数组a的最后一位为1（表示初始值为1）/*** @brief * 为了加快计算速度，我们将乘法分为两部分：* 1. 前num1轮，每次乘以2^32* 2. 后num2轮，每次乘以2*/// 前num1轮，每次乘以2^32for (int i = 1; i <= num1; i++) {// 对数组a的每一位乘以2^32for (int j = 500; j >= 1; j--) a[j] *= x;// 处理进位for (int j = 500; j >= 1; j--) {a[j - 1] += a[j] / 10; // 将进位加到前一位a[j] %= 10; // 当前位只保留个位数}}// 后num2轮，每次乘以2for (int i = 1; i <= num2; i++) {// 对数组a的每一位乘以2for (int j = 500; j >= 1; j--)a[j] *= 2;// 处理进位for (int j = 500; j >= 1; j--) {a[j - 1] += a[j] / 10; // 将进位加到前一位a[j] %= 10; // 当前位只保留个位数}}a[500]--; // 最后一位减1（因为2^p - 1）// 输出2^p - 1的位数cout << (int)(p * log10(2) + 1) << endl;// 输出2^p - 1的值，每50位换行for (int i = 1; i <= 500; i++) {cout << a[i];if (i % 50 == 0) // 每50位换行cout << endl;}return 0;
}
【运行结果】
1279
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087