vijosP1223麦森数

链接：https://vijos.org/p/1223

【思路】

快速幂+高精乘。

计算2^p-1可以快速幂的方法在O(logn)的时间内出解，限于数据范围我们需要用到高精度。

注意：

1、2^p-1的位数为 (int) (log10(2)*n-1)。

2、计算只要到达500位即可。

3、结果的个位一定不为1，因为2^p-1二进制中2^0号位一定为1。

4、strut的初始化。

【代码】

 #include<iostream>

 #include<cstring>

 #include<cmath>

 using namespace std;

 struct Bign{

     int len;

     int num[];

     Bign() { memset(num,,sizeof(num)); };  //init

 };

 int n;

 int LEN=;

 Bign ans,c,tmp;

 void multi(Bign& a, Bign b)

 {

     memset(c.num,,sizeof(c.num));

     for(int i=;i<LEN;i++)

       for(int j=;j<LEN;j++)

        if(i+j<LEN)

         c.num[i+j] += a.num[i]*b.num[j];

        else

           break;

     for(int i=;i<LEN;i++){

         c.num[i+] += c.num[i]/;

         c.num[i] %= ;

     }

     a=c;

 }

 int main()

 {

     cin>>n;

     cout<<(int)(n*log10()+)<<"\n";

     tmp.len=; tmp.num[]=;

     ans.len=; ans.num[]=;

     while(n) {

         if(n&) multi(ans,tmp);

         multi(tmp,tmp);

         n>>=;

     }

     ans.num[]--;

     int cnt=;

     for(int i=LEN-;i>=;i--) {

         cout<<ans.num[i];

         if(++cnt%==) cout<<endl;

     }

     return ;

 }