形如 2P−12P−1 的素数称为麦森数，这时 PP 一定也是个素数。但反过来不一定，即如果 PP 是个素数，2P−12P−1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。
任务：输入 P(1000<P<3100000)P(1000<P<3100000)，计算 2P−12P−1 的位数和最后 500500 位数字（用十进制高精度数表示）
输入格式
文件中只包含一个整数 P(1000<P<3100000)P(1000<P<3100000)
输出格式
第一行：十进制高精度数 2P−12P−1 的位数。
第 2∼112∼11 行：十进制高精度数 2P−12P−1 的最后 500500 位数字。（每行输出 5050 位，共输出 1010 行，不足 500500 位时高位补 00）
不必验证 2P−12P−1 与 PP 是否为素数。
输入输出样例
输入 #1复制
1279
输出 #1复制
386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087
这个题目意思很明确，这里我们引入一个数学知识点 2的n次方位数=
N*log2 +1
2的n次方的个位数规律是：[ N*log2 ] +1 ]，其中[ ]表示取整，log2=0.30102999566。例如，2的30次方的个位数是10，2的5次方的个位数是2，2的200次方的个位数是611。2的幂次是由1×2的1次方乘以2的（n-1）次方来求得的，例如2的3次方=4，2的4次方=16，以此类推2
然后我们观察2^p-1里面这个 -1该如何处理呢？因为2的指数是的个位必然是不为0的偶数，所以直接减就好了，这也是很容易想到的，很容易想出这么一个代码
#include<stdio.h>
#include<math.h>
void f(int a[500]){
for(int i=1;i<=500;i++){
a[i]=a[i]*2;
}
for(int i=1;i<=500;i++){
if(i!=500){
if(a[i]>=10){
a[i+1]=a[i]/10+a[i+1];
a[i]=a[i]%10;
}
}else a[i]=a[i]%10;
}
}
int main(){int p;
scanf("%d",&p);
int count=p*log10(2)+1;
int a[501]={0};
a[1]=1;
for(int i=1;i<=p;i++)
f(a);
a[1]--;
printf("%d\n",count);
for(int i=500;i>=1;i--){
if((i-1)%50!=0)printf("%d",a[i]);
else printf("%d\n",a[i]); }
return 0;
}然而只对了6个测试点其他剩下4个测试点都是"TLE"，很显然复杂度太高了，还有没有什么优化的方案呢，我冥思苦想不妨先判断p是奇数还是偶数，然后将其加速1倍，看看能不能行！（抱歉找不到代码了）
对了7个测试点！也就是说思路没错，既然能加速1倍那么为什么不能加速10倍！
最终AC代码
#include<stdio.h>
#include<math.h>
void f(int a[500],int k){
for(int i=1;i<=500;i++){
a[i]=a[i]*k;//加速10倍数
}
for(int i=1;i<=500;i++){
if(i!=500){
a[i+1]=a[i]/10+a[i+1];
a[i]=a[i]%10;
}
else a[i]=a[i]%10;
}
}
int main(){int p;
scanf("%d",&p);
int count=p*log10(2)+1;
int a[501]={0};int k=pow(2,10);//加速预备 ，注意
a[1]=1;int p0=p%10;
for(int i=1;i<=p/10;i++)
f(a,k);
while(p0--){for(int i=1;i<=500;i++){
a[i]=a[i]*2;
}//剩下需要乘的2，单独乘法！注意
for(int i=1;i<=500;i++){
if(i!=500){
a[i+1]=a[i]/10+a[i+1];
a[i]=a[i]%10;
}
else a[i]=a[i]%10;
}
}
a[1]--;
printf("%d\n",count);
for(int i=500;i>=1;i--){
if((i-1)%50!=0)printf("%d",a[i]);
else printf("%d\n",a[i]);
}
return 0;
}实际上加速20倍也是可以的，后来我又想加速100倍，发现2的100次数位数太大了，int装不下……
学习的过程就是不断试错与探索的！
