题目描述
形如 $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;
}