麦森数 - 高精度+快速幂

快速幂模板：

求a^b:

int ans=1;
while(b!=0){
    if(b&1)ans*=a;
    b>>=1;
    a*=a;
}
printf("%d\n",ans);

高精度乘高精度模板：

void cheng(int a[],int b[]){
    int c[500]={0};
    c[0]=a[0]+b[0];
    for(int i=0;i<a[0];i++){
        for(int j=0;j<b[0];j++){
            c[i+j+1]+=a[i+1]*b[i+1];
            if(c[i+j+1]>10){
                c[i+j+2]+=c[i+j+1]/10;
                c[i+j+1]%=10;
            }
        }
    }
    while(c[k]==0)c[0]--;
}

代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int ans[1000000],a[1000000];

void cheng(int x[],int y[]){
    int c[100000]={0};
    c[0]=x[0]+y[0];
    if(c[0]>500)c[0]=500;

    for(int i=0;i<x[0];i++){
        for(int j=0;j<y[0];j++){
            c[i+j+1]+=x[i+1]*y[j+1];
            if(c[i+j+1]>10){
                c[i+j+2]+=c[i+j+1]/10;
                c[i+j+1]%=10;
            }
        }
    }
    for(int i=0;i<=c[0];i++)x[i]=c[i];
}

void print(){
    int q=500;
    for(int i=0;i<10;i++){
        for(int j=0;j<50;j++){
            printf("%d",ans[q]);
            q--;
        }
        printf("\n");
    }
    printf("\n");
}
int main(){
    int p;
    scanf("%d",&p);
    printf("%d\n",(int)(log10(2)*p+1));

    ans[0]=ans[1]=a[0]=1;a[1]=2;
    while(p!=0){
        if(p&1!=0)cheng(ans,a);
        p>>=1;
        cheng(a,a);
    }
    ans[1]--;
    print();
}

本题的收获和遇到的陷阱：

1.求2^p的位数：

2.在cheng()函数中，数组ans，只用保留前500位就可以了不然会超时

3.在cheng()函数中开始设数组c的大小为600，结果出现了“程序停止工作”

原因可能为：

a.野指针，你使用的指针指向未知区域
b.scanf函数输入整形、字符……的时候缺少了&
c.缓冲区溢出，也就是说你使用数组时不经意间越界了

显然我犯得是c错，虽然理论上数组c只用前500位就行了，但是在x与y数组相乘的时候位数会远远大于500，所以要开大点数组