麦森数

算法训练 麦森数描述 　　形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。 　　任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）输入输入描述: 　　文件中只包含一个整数P（1000<P<3100000） 输入样例: 1279输出 输出描述: 　　第一行：十进制高精度数2P-1的位数。 　　第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0） 　　不必验证2P-1与P是否为素数。 输出样例: 386 00000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000 00000000000000104079321946643990819252403273640855 38615262247266704805319112350403608059673360298012 23944173232418484242161395428100779138356624832346 49081399066056773207629241295093892203457731833496 61583550472959420547689811211693677147548478866962 50138443826029173234888531116082853841658502825560 46662248318909188018470682222031405210266984354887 32958028878050869736186900714720710555703168729087 第一问求2^p-1位数 考虑到数据范围1000~3100000，爆搜肯定tle 2^p-1在求数位时等于2的p次方，因其不存在退位情况 将其化为10的a次方，数位即为a+1， 同时有：2的p次方=10的a次方 ，即a=log10(2)*p; 第二问 高精度乘法+递推求幂次方

#include<bits/stdc++.h>
using namespace std;
#define ll long long
long long a[1500],b[1500];
void quickpow(ll n)
{
    if(!n)return;
    quickpow(n/2);
    if(n%2==0)
    for(int i=1;i<=500;++i)
     for(int j=1;j<=500;++j)
      a[i+j-1]=a[i+j-1]+b[i]*b[j];
  else
    for(int i=1;i<=500;++i)
     for(int j=1;j<=500;++j)
      a[i+j-1]=a[i+j-1]+b[i]*b[j]*2;
    for(int i=1;i<=500;++i)
    {
    b[i]=a[i]%10;
        a[i+1]=a[i+1]+a[i]/10;    
    }
    memset(a,0,sizeof(a));
}
int main()
{
    ll p;
    cin>>p;
    printf("%lld\n",(ll)(log10(2)*p+1));
    b[1]=1;
    quickpow(p);
    for(int i=500;i>1;--i)
    {
        cout<<b[i];
        if(i%50==1)cout<<endl;
    }
    cout<<b[1]-1;
    return 0;
}