P1045 麦森数

admin

题目描述
形如 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位数字。（每行输出50位，共输出10行，不足500位时高位补0）

输入输出样例
输入样例#1：
1279
输出样例#1：
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

张笑宇

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int mx=550;
   
5. int s[mx],t[mx],a[2*mx];
   
6. int i,j,n,x;
   
7. int main()
   
8. {
   
9.     cin>>n;
   
10.     cout<<(int)(log10(2)*n+1)<<endl;
    
11.     s[0]=1,t[0]=2;
    
12.     while (n>0)
    
13.     {
    
14.         if (n%2==1)
    
15.         {
    
16.             n--;
    
17.             ///s=s*t;
    
18.             for (i=0; i<=mx-1; i++) a[i]=0;
    
19.             for (i=0; i<=mx-1; i++)
    
20.                 for (j=0; j<=mx-1; j++)
    
21.                     a[i+j]+=s[i]*t[j];
    
22.             for (i=0; i<=mx-2; i++)
    
23.             {
    
24.                 x=a[i];
    
25.                 a[i]=x%10;
    
26.                 a[i+1]+=x/10;
    
27.             }
    
28.             for (i=0; i<=mx-1; i++) s[i]=a[i];
    
29.         }
    
30.         n=n/2;
    
31.         ///t=t*t;
    
32.         for (i=0; i<=mx-1; i++) a[i]=0;
    
33.         for (i=0; i<=mx-1; i++)
    
34.             for (j=0; j<=mx-1; j++)
    
35.                 a[i+j]+=t[i]*t[j];
    
36.         for (i=0; i<=mx-2; i++)
    
37.         {
    
38.             x=a[i];
    
39.             a[i]=x%10;
    
40.             a[i+1]+=x/10;
    
41.         }
    
42.         for (i=0; i<=mx-1; i++) t[i]=a[i];
    
43.     }
    
44.     ///cout<<s;
    
45.     s[0]--;
    
46.     for (i=499;i>=0;i--)
    
47.     {
    
48.         cout<<s[i];
    
49.         if (i%50==0) cout<<endl;
    
50.     }
    
51.     return 0;
    
52. }
    

复制代码

吴语林

1. #include<iostream>
   
2. #include<cstdio>
   
3. #include<cstring>
   
4. #include<algorithm>
   
5. #include<cmath>
   
6. using namespace std;
   
7. int p,a[100002],b[520];
   
8. void su(int n)
   
9. {
   
10.         int i,j;
    
11.         if(n==0)
    
12.                 return;
    
13.         su(n/2);
    
14.         for(i=1;i<=500;i++)
    
15.                 for(j=1;j<=500;j++)
    
16.                         if(n%2==0)
    
17.                                 a[i+j-1]=a[i+j-1]+b[i]*b[j];
    
18.                         else
    
19.                                 a[i+j-1]=a[i+j-1]+b[i]*b[j]*2;
    
20.         for(i=1;i<=500;i++)
    
21.         {
    
22.                 b[i]=a[i]%10;
    
23.                 a[i+1]=a[i+1]+a[i]/10;
    
24.         }
    
25.         memset(a,0,sizeof(a));
    
26. }
    
27. int main()
    
28. {
    
29.         int i;
    
30.         scanf("%d",&p);
    
31.         b[1]=1;
    
32.         su(p);
    
33.         cout<<int((log(2)/log(10))*p+1)<<endl;
    
34.         for(i=500;i>1;i--)
    
35.         {
    
36.                 printf("%d",b[i]);
    
37.                 if(i%50==1)
    
38.                         printf("\n");
    
39.         }
    
40.         printf("%d",b[1]-1);
    
41.         return 0;
    
42. }

复制代码

倚窗倾听风吹雨

1. #include<iostream>
   
2. #include<cmath>
   
3. using namespace std;
   
4. const int M=1030;
   
5. int a[M],b[M],p;
   
6. void mul(int x[],int y[])
   
7. {
   
8.     int c[M],k=0;
   
9.     for(int i=0;i<=M-1;i++)c[i]=0;
   
10.     for(int i=1;i<=510;i++)
    
11.         for(int j=1;j<=510;j++)
    
12.     {
    
13.         c[i+j-1]+=x[i]*y[j]+k;
    
14.         k=c[i+j-1]/10;
    
15.         c[i+j-1]%=10;
    
16.     }
    
17.     for(int i=500;i>=1;i--)x[i]=c[i];
    
18. }
    
19. int main()
    
20. {
    
21.     cin>>p;
    
22.         cout<<int(log10(2)*p+1)<<endl;
    
23.     a[1]=1;
    
24.     b[1]=2;
    
25.     while(p>0)
    
26.     {
    
27.         if(p%2!=0)mul(a,b);
    
28.         mul(b,b);
    
29.         p/=2;
    
30.     }
    
31.     a[1]--;
    
32.     for(int i=500;i>=1;i--)
    
33.     {
    
34.         p++;
    
35.         cout<<a[i];
    
36.         if(p==50)
    
37.         {
    
38.             cout<<endl;
    
39.             p=0;
    
40.         }
    
41.     }
    
42. }
    

复制代码