题目描述
形如 $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是否为素数。
输入输出样例
输入 #1
1279输出 #1
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087题目分析
题目需要我们解决两个问题
- 位数
- 最后500位数字
首先对于位数，我们 $2^p-1$ 的位数一定与 $2^p$ 的位数相同，因为 $2^p$ 不可能出现个位为0的情况。所以只需要求 $2^p$ 的位数即可。
对于十进制数字$x$，它对应的位数为 $\lfloor \log_{10}^x + 1\rfloor$，所以$2^p$ 的位数为 $\lfloor \log_{10}^{2^p}+1\rfloor$。
已知对数公式
$$ \log_a^{b^c}=c\log_a^b $$
所以
$$ \log_{10}^{2^p}=p\log_{10}^2 $$
所以 $2^P$的位数等于 $\lfloor p\log_{10}^2+1\rfloor$ 。而cmath存在函数log10(x) 可以求解 $log_{10}x$ 的值。
所以位数等于int(p*log10(2)+1) 。
其次，再来解决第二个问题。求后500位的内容。500位的数字对于现有的整数类型来说还是太大了，所以采用高精度的方式处理，而且我们每次只需处理后500位即可。将高精度乘二的过程重复p次即可。理论上的执行次数是 $500p$ 。而本题中p的范围的限制，导致总的次数达到 $1.5 \times 10^9 $ 。
此时，可以考虑压位高精的方式进行处理，使用 long long 类型，每个元素保留10位的数字，500 位数字，只需50个元素即可，降低总次数至 $10^8$ 的量级，即可满足题目要求。
代码实现
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 M = 1e10;
int p;
i64 num[55]={1};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>p;
for(int i=1;i<=p;i++){//计算2^p ，压位高精
int jw=0;
for(int j=0;j<50;j++){//逐位乘2
num[j]=jw+num[j]*2;
jw=num[j]/M;
num[j]%=M;
}
}
num[0]-=1;//求2^p - 1,最低位减1
printf("%d\n",(int)(p*log10(2)+1));//计算位数
for(int i=49;i>=0;i--){//从高位输出，10位一组，不足10位用0补齐
printf("%010lld",num[i]);
if(i%5==0) printf("\n");//50个一行
}
return 0;
}快速幂实现
可发现第二问实际要求的是 $2^p$ 那么我们可以使用分治的思路进行求解，也就是快速幂的方式进行快速幂的求解。
快速幂模板
//分治
int mypow(int a,int n){
if(n==0) return 1;
int t=mypow(a,n/2);
if(n&1) return t*t*a;
return t*t;
}
//倍增
int mypow(int a,int n){
int ans=1;
while(n){
if(n&1) ans=ans*a;
a=a*a;
n>>=1;
}
return ans;
}从模板中可发现只涉及到乘法的计算，结合本道题的数据范围，可以采用高精度乘法的方式进行处理。对于最后的减1，由于 $2^p$ ，p的值 $>1000$ 所以一定为偶数，减1必不可能导致退位所以，直接在高精度数字的最低位减1即可，不用加入高精度减法的计算。
计算过程中需要注意最终只需要保留最后500位，那么高精度乘法计算过程中，最多也只需要低500位参与计算即可。整体估算一下时间复杂度 ,高精度乘法部分一次计算最多为 $500^2$ ，快速幂部分复杂度为 $\log p$ ，整体为 $O(m\log p)$ ，m为数字位数,P为次幂数。根据本题数据规模 大致为 $10^6$的量级，必压位高精的速度更快。
代码实现
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const int N = 1e5 + 5;
struct node {
int num[505]; // 高精度数值部分
int len; // 高精度数字位数
friend node operator*(const node &A, const node &B) {
// 重载* 计算高精度乘法 （模拟乘法竖式计算）
node C = {0};
int la = min(500, A.len), lb = min(500, B.len);
for (int i = 0; i < la; i++) {
for (int j = 0; j < lb; j++) {
if (i + j > 500) continue;
C.num[i + j] += A.num[i] * B.num[j];
C.num[i + j + 1] += C.num[i + j] / 10;
C.num[i + j] %= 10;
}
}
C.len = min(500, la + lb);
return C;
}
};
// node mypow(node A, int p) { // 倍增快速幂（高精度）
// node ans = {{1}, 1}; // 1
// while (p) {
// if (p & 1) ans = ans * A;
// A = A * A;
// p >>= 1;
// }
// return ans;
// }
node mypow(node A, int p) { // 分治快速幂（高精度）
if (p == 0) return {{1}, 1}; // 2^0 = 1
node t = mypow(A, p / 2);
if (p & 1) return t * t * A;
return t * t;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int p;
cin >> p;
// Q1: 位数
cout << int(p * log10(2) + 1) << endl;
// Q2: 2^p - 1
node ans = mypow({{2}, 1}, p); // 计算2^p
ans.num[0]--; // 2^p - 1
for (int i = 499; i >= 0; i--) {
cout << ans.num[i];
if (i % 50 == 0) cout << "\n";
}
return 0;
}