[NOIP 2003 普及组] 麦森数

知识点

高精度、快速幂、对数

解题思路

位数是floor(P·log10(2))+1。末500位等价于模10^500计算2^P再减1，用500个十进制数位保存并进行截断乘法和二进制快速幂。计算完成后按高位到低位每50位输出一行，高位不足补0。

正确性说明

2^P不是10的正整数次幂，所以减1不改变十进制位数。模10^500的乘法与原数相乘后只取末500位等价，快速幂保持结果乘积和剩余幂的不变式，故得到正确尾部。P>0时2^P末位为2/4/8/6，减1无需向更高位借位。

易错点

不能验证P或2^P-1是否为素数；尾部必须500位并保留前导零；乘法每次截断，不能存储整个2^P。

复杂度

快速幂O(500² log P)时间，O(500)空间；位数使用long double。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
using Big=array<int,500>;Big mul(const Big&a,const Big&b){array<int,500>c{};for(int i=0;i<500;i++)if(a[i])for(int j=0;i+j<500;j++)c[i+j]+=a[i]*b[j];Big r{};for(int i=0;i<500;i++){if(i+1<500)c[i+1]+=c[i]/10;r[i]=c[i]%10;}return r;}int main(){int p;cin>>p;cout<<(long long)(p*log10l(2.0L))+1<<'\n';Big a{},r{};a[0]=2;r[0]=1;for(int q=p;q;q>>=1,a=mul(a,a))if(q&1)r=mul(r,a);--r[0];for(int i=499;i>=0;i--){cout<<r[i];if(i%50==0)cout<<'\n';}}