问题描述
形如2p-1 的素数称为麦森数,这时P 一定也是个素数。但反过来不一定,即如果P 是
个素数。2p-1 不一定也是素数。到1998 年底,人们已找到了37 个麦森数。最大的一个是
P=3021377,它有909526 位。麦森数有许多重要应用,它与完全数密切相关。
你的任务:输入P (1000<P<3100000) , 计算2p-1 的位数和最后500 位数字(用十进制高
精度数表示)
输入数据
只包含一个整数P(1000<P<3100000)
输出要求
第1 行:十进制高精度数2p-1 的位数。 第2-11 行:十进制高精度数2p-1 的最后500
位数字。(每行输出50 位,共输出10 行,不足500 位时高位补0)
不必验证2p-1 与P 是否为素数。
输入样例
1279
输出样例
386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
const int LEN = 125;
void multiply(int* a, int* b){
int c[LEN];
memset(c, 0, sizeof(c));
int nCarry, total = 0;
for(int i = 0; i < LEN; i++){
nCarry = 0;
for(int j = 0; j < LEN - i; j ++){//因为只要500位,所以算到125-i-1就够了
total = c[i + j] + a[j] * b[i] + nCarry;
c[i + j] = total % 10000;
nCarry = total / 10000;
}
}
memcpy(a, c, sizeof(c));
}
int main(){
int p;
cin >> p;
cout << (int)(p * log10(2)) + 1 << endl;
int anPow[LEN];
int result[LEN];
anPow[0] = 2;
result[0] = 1;
for(int i = 1; i < LEN; i++){
anPow[i] = 0;
result[i] = 0;
}
while(p > 0){
if(p & 1)
multiply(result, anPow);
p>>= 1;
multiply(anPow, anPow);
}
result[0] --;
for(int i = LEN - 1; i >= 0; i--){
if(i % 25 == 12)
printf("%02d\n%02d", result[i] / 100, result[i] % 100);
else{
printf("%04d", result[i]);
if(i % 25 == 0)
cout << endl;
}
}
return 0;
}
分享到:
相关推荐
需要杰哥讲解的毕设js代码
C++自制小游戏《杰哥和阿伟》源码(cpp) C++小游戏,由哔哩哔哩的梗制作而成,切勿当真哦~ 游戏内行为请勿模仿! 原创小游戏,请勿转载或整改~ 记得关注@Ender_momo,短时间内将发布制作过程
杰哥两套卷.rar
有跟我一样看不懂代码,只能盲抄来理解的吗,杰哥看到了莫生气我自己现在真写不了好了,今天的案例与while语句有关
本人收集的几套百度笔试题。 doc格式,需要找工作的可以看看
Ceph是一个开源的分布式文件系统。因为它还支持块存储、对象存储,所以很自然的被用做云计算框架openstack或cloudstack整个存储后端。当然也可以单独作为存储,例如部署一套集群作为对象存储、SAN存储、NAS存储等。...
python深度学习-pandas
杰哥应急响应ppt
百度google 笔试题汇总,全是word 文档。对找实习有很多好处的
C语言35页第4题第2小问.exe
大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见公粽号 :杰哥的无人驾驶便利店。
该文档为配套的【杰哥日常小工具】字符串处理工具的登录效验码,下载工具后可登录解码该文档信息获取管理员或VIP登录码
文章目录1 故事的开局2 杰哥的表演2.1 sl2.2 htop2.3 gcp2.4 hollywood2.5 cmatrix2.6 asciiview2.7 ninvaders2.8 bastet2.9 pipe2.10 oneko3 博主的炸弹4 总结 1 故事的开局 周末到了,部门里几个小伙伴约好了一起...
matlab软件下载:lingo教程数学建模Lingo系列视频(爆肝杰哥): Lingo(1)基础篇:BV1CT4y177qS Lingo(2)入门篇:BV1U
无人驾驶车辆轨迹跟踪控制综述型参考英文文献!大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见公粽号 :杰哥的无人驾驶便利店
无人驾驶车辆轨迹跟踪控制综述型参考英文文献!大家可以通过这篇文献对控制领域有一个大体的认知。 更多炸裂内容,详见弓粽Hao :杰哥的无人驾驶便利店