描述
形如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位数字。（一行输出，不足500位时高位补0）
不必验证2^P-1与P是否为素数。
样例输入
1279
样例输出
386
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
题意
先输出十进制高精度数2^P-1的位数再输出最后500位
题解
这里求位数我推了好久，其实求位数有个公式：log10(a)*p+1，表示a^p的位数
这里-1不影响总位数，因为2的倍数末尾只可能是2，4，6，8
算500位采用快速幂的思想：2^5==(2^2)^2*2 其中2^2==(2^1)^2
然后模拟一下乘2和平方即可，注意算平方的时候不能越界
代码
#include<stdio.h>
#include<math.h>
#include<string.h>
int a[];
void digui(int x){//快速幂思想
if(x/!=)
digui(x/);
pifang();
if(x%==)
cheng();
}
void cheng(){//乘2
int i;
for(i=;i>=;i--)
a[i]*=;
for(i=;i>=;i--){
if(a[i]>=){
a[i-]+=a[i]/;
a[i]%=;
}
}
}
void pifang(){//平方
int i,j,p[];
memset(p,,sizeof(p));
for(i=;i>=;i--)
for(j=;j>=;j--)
if(i+j->=)//注意这里不能越界
p[i+j-]+=a[i]*a[j];
for(i=;i>=;i--){
if(p[i]>=){
p[i-]+=p[i]/;
p[i]%=;
}
}
for(i=;i<=;i++)
a[i]=p[i];
} int main(){
int i,p;
memset(a,,sizeof(a));
scanf("%d",&p);
printf("%d\n",(int)(p*log10())+);//直接套公式
a[]=;
digui(p);
a[]--;
for(i=;i<=;i++)
printf("%d",a[i]);
puts("");
return ;
}