luogu P1045 麦森数

1. 题目大意

题目介绍了什么是麦森数，就是当$2^p-1$2p−1为素数时，这个时候$p$p也一定是素数，然而反过来却不一定。到1988年，人们已找到了37个麦森数，最大的$p=3021377$p=3021377，它有909526位。
麦森数还有很多重要应用，它与完全数密切相关。给个维基链接：
梅森数
题目要求：输入$p(1000<p<3100000)$p(1000<p<3100000)，计算$2^p-1$2p−1的位数和最后500位数字。

2. 解题思路

蒟蒻杀某前几天刚总结高精度算法（抄了板子），因此可以派上用场了，那先解释我是怎么复杂的搞出这道题的。

1. 首先是位数，当然我们想知道一个十进制的数的位数，可以有一百种姿势知道，就拿$10^n$10n来说，位数是$n+1$n+1。对于梅森数，显然位数是$2^p$2p的位数，因为各位不可能为0，所以减1，位数不变的。因此我们可以通过对数将2位底的指数变为10为底，如下：
   $2^p=(10^{log_{10}2})^p=10^{log_{10}2*p}$2p=(10log10​2)p=10log10​2∗p
   因此位数就是$log_{10}2*p+1$log10​2∗p+1。第一个问题搞定。
2. 然后输出最后500位，看洛谷题解，神犇脱口裸高精快速幂，啥？蒟蒻一脸懵逼。因此我把快速幂有复习了一遍，高精复习了一遍，就开始写了，由于涉及到高精乘高精，我就按照高精乘数的板子改，我就一位一位乘呗，每次外部循环加1，临时存储的数组也进一位存储，每次累加给答案里。如下：
   
   其实就是模拟手算过程。很清晰，这里需要注意的是，高精乘高精，大小要开原来的两倍即可。
   然后快速幂就是按照模板来。

3.代码展示

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001; //乘法开两倍,吃大亏一开始
int sum[MAXN]={1,1},temp1[MAXN],temp[MAXN];
void add(int temp[]){
    int t=0,i;
    for(i=1;i<=temp1[0] || t || i<=temp[0];i++){
        if(i>500) break;
        t+=temp1[i];
        if(i<=temp[0]) t+=temp[i];
        temp1[i]=t%10;
        t/=10;
    }
    temp1[0]=max(temp1[0],i-1);
}
void muti(){ //高精乘高精，逐位相乘
    for(int i=1;i<=sum[0];i++) {
        memset(temp,0,sizeof temp);
        int t=0,j;
        for (j = 1; j <= sum[0] || t; j++) {
            //if (j > 500) break;
            if (j <= sum[0]) t += sum[j] * sum[i];
            temp[j+i-1] = t % 10;
            t /= 10;
        }
        temp[0]=max(temp[0],j+i-2);
        temp1[0]=max(temp1[0],j-1);
        add(temp);//乘结束之后，记得累加上去
        //if(temp1[0]>=500) break;
    }
    memcpy(sum,temp1,sizeof sum); //随后把答案复制给最后的数组
    memset(temp1,0,sizeof temp1);
}
void muti2(){ //sum[0]记录位数
    int t=0,i;
    for(i=1;i<=sum[0] || t;i++){
        if(i<=sum[0]) t+=sum[i]*2;
        sum[i]=t%10;
        t/=10;
    }
    sum[0]=max(sum[0],i-1);
}
//递归多香！
void pow_mod(int P){
  if(P==0) return;
  pow_mod(P>>1);
  muti();
  if(P%2)muti2();
}
//迭代版本
/*
 void pow_mod(int P){
    int temp[MAXN]={1,1};
    while(P>0){
        if(P%2) temp*=sum;//这里需要写高精*高精
        muti();
        P>>=1;
    }
 }
 */
int main()
{
    int P;
    cin>>P;
    pow_mod(P);
    sum[1]-=1;
    cout<<(int)(log10(2)*P)+1<<endl;
    for(int i=500;i>0;i--){
          if(i!=500 && i%50==0)  cout<<endl<<sum[i];
          else cout<<sum[i];
    }
    return 0;
}

4. 高精×高精

说到底还是要记录下这个板子的，其实就是先计算每位的值，然后在进位，竟然没想到移动指针即可，还打了高精+高精进去，蠢啊！下面按照答案，自己打了下板子，应该没问题（逃

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6;
int sum[MAXN]={1,1},sav[MAXN];
//高精乘高精
vector<int> mul_2(vector<int>&a,vector<int>&b){
    vector<int> c(a.size()+b.size(),0);
    for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++) c[i+j]+=a[i]*b[j];
    for(int i=0;i<c.size()-1;i++){
        c[i+1]+=c[i]/10;
        c[i]%=10;
    }
    while(c,size()>0 && c.back()==0) c.pop_back();
}
//另一种写法（高精乘高精）
void muti_2(int temp[]){
    for(int i=1;i<=sum[0];i++)for(int j=1;j<=temp[0];j++) sav[i+j-1]+=sum[i]*temp[j];
    int count=sum[0]+temp[0];
    for(int i=1;i<count;i++) sav[i+1]+=sav[i]/10,sav[i]%=10;
    //统计位数
    while(count>0 && sav[count]==0) count--;
    sav[0]=max(sav[0],count);
    memcpy(sum,sav,sizeof sav);
}

5. 其他答案

快速幂+高精×高精

#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int f[1001],p,res[1001],sav[1001];//乘法要开两倍长度
void result_1()
{
    memset(sav,0,sizeof(sav));
    for(register int i=1;i<=500;i+=1)
        for(register int j=1;j<=500;j+=1)
            sav[i+j-1]+=res[i]*f[j];//先计算每一位上的值（不进位）
    for(register int i=1;i<=500;i+=1)
    {
        sav[i+1]+=sav[i]/10;//单独处理进位问题，不容易出错
        sav[i]%=10;
    }
    memcpy(res,sav,sizeof(res));//cstring库里的赋值函数，把sav的值赋给res
}
void result_2()//只是在result_1的基础上进行了细微的修改
{
    memset(sav,0,sizeof(sav));
    for(register int i=1;i<=500;i+=1)
        for(register int j=1;j<=500;j+=1)
            sav[i+j-1]+=f[i]*f[j];
    for(register int i=1;i<=500;i+=1)
    {
        sav[i+1]+=sav[i]/10;
        sav[i]%=10;
    }
    memcpy(f,sav,sizeof(f));
}
int main()
{
    scanf("%d",&p);
    printf("%d\n",(int)(log10(2)*p+1));
    res[1]=1;
    f[1]=2;//高精度赋初值
    while(p!=0)//这里用的我写的迭代模板
    {
        if(p%2==1)result_1();
        p/=2;
        result_2();
    }
    res[1]-=1;
    for(register int i=500;i>=1;i-=1)//注意输出格式，50个换一行，第一个不用
        if(i!=500&&i%50==0)printf("\n%d",res[i]);
        else printf("%d",res[i]);
    return 0;
}

6. 总结

一题一下午，酸爽啊！