【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 108466
  • 排名 - 229

最新评论

阅读排行榜

评论排行榜

形如2^P-1的素数称为麦森数,这时P一定也是个素数。但反过来不一定,即如果P是个素数,2^P-1不一定也是素数。到1998年底,人们已找到了37个麦森数。最大的一个是P=3021377,它有909526位。麦森数有许多重要应用,它与完全数密切相关。
任务:从文件中输入P(1000<P<3100000),计算2^P-1的位数和最后500位数字(用十进制高精度数表示)

input:
文件中只包含一个整数P(1000<P<3100000)

output:
第一行:十进制高精度数2^P-1的位数。
第2-11行:十进制高精度数2^P-1的最后500位数字。(一行输出,不足500位时高位补0)
不必验证2^P-1与P是否为素数。

input:
1279

output:
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

【参考程序】:
#include<iostream>
#include
<cmath>
using namespace std;
int a[502
];
int
 n;
void work(int
 p)
{
        
int b[1001
];
        
if (p==1
)
        {
                a[
1]=2
;
                
return
 ;
        }
        memset(b,
0,sizeof
(b));
        
if (p%2==1
)
        {
                work(p
/2
);
                
for (int i=1;i<=500;i++
)
                        
for (int j=1;j<=500;j++
)
                                b[i
+j-1]+=a[i]*
a[j];
                
for (int i=1;i<=501;i++
)
                {
                        a[i]
=b[i]*2
;
                        a[i]
+=a[i-1]/10
;
                        a[i
-1]%=10
;
                }
        }
        
else
 
        {
                work(p
/2
);
                
for (int i=1;i<=500;i++
)
                        
for (int j=1;j<=500;j++
)
                                b[i
+j-1]+=a[i]*
a[j];
                
for (int i=1;i<=501;i++
)
                {
                        a[i]
=b[i]+a[i-1]/10
;
                        a[i
-1]%=10
;
                }
        }
        a[
501]=0
;
}
int
 main()
{
        scanf(
"%d",&
n);
        printf(
"%0.0lf\n",floor(n*log(2.0)/log(10.0))+1
);
        work(n);
        
for (int i=500;i>=2;i--) printf("%d"
,a[i]);
        printf(
"%d\n",a[1]-1
);
        
return 0
;
}

posted on 2009-05-01 16:33 开拓者 阅读(583) 评论(0)  编辑 收藏 引用 所属分类: NOIP历届题目

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理