luogu 1045 麦森数

题目大意：

从文件中输入P（1000<P<3100000），计算2^P−1的位数和最后500位数字（用十进制高精度数表示）

思路：

一道高精度练习题

其中位数是一个结论位数=[P*log2]+1

然后就是高精度，因为作死的压位打了好久

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 2139062143

 #define ll long long

 #define MAXN 6010

 #define MOD 10000

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 struct bign

 {

     int len,num[];

     bign(){len=;memset(num,,sizeof(num));}

     void Print()

     {

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

             if(i%==) printf("%02d\n%02d",num[i]/,num[i]%);

             else if(i%==) printf("%04d\n",num[i]);

             else printf("%04d",num[i]);

         printf("%04d",num[]-);

     }

 };

 bign mul(bign a,bign b)

 {

     bign res;int t;

     //cout<<"a: ";a.Print();cout<<"b: ";b.Print();

     for(int i=;i<=a.len;i++)

         for(int j=;j<=b.len;j++)

         {

             t=a.num[i]*b.num[j];

             if(i+j<=)

                 if(i+j<) res.num[i+j]+=t,res.num[i+j+]+=res.num[i+j]/MOD,res.num[i+j]%=MOD;

                 else res.num[i+j]+=t,res.num[i+j]%=MOD;

         }

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

         if(res.num[i]) res.len=i;

     return  res;

 }

 void q_pow()

 {

     bign ans,t;ans.num[]=,t.num[]=;

     while(n)

     {

         if(n&) ans=mul(ans,t);

         t=mul(t,t);

         n>>=;

     }

     ans.Print();

 }

 int main()

 {

     n=read();

     printf("%d\n",(int)(n*0.30103)+);

     q_pow();

 }

巴特西

luogu 1045 麦森数

最新文章

热门文章