首页 > 代码库 > 麦森数
麦森数
题目描述
形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）
输入输出格式
输入格式：
文件中只包含一个整数P（1000<P<3100000）
输出格式：
第一行：十进制高精度数2^P-1的位数。
第2-11行：十进制高精度数2^P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2^P-1与P是否为素数。
输入输出样例
输入样例#1：
1279
输出样例#1：
38600000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
思路：某种数学公式+高精乘（压位+阶梯因数）
代码实现：
1 #include<cmath> 2 #include<cstdio> 3 #define mod 100000 4 int p,s=1650; 5 long long a[110],b[110],c[300],d; 6 void write(long long x,int k){ 7 if(!k) return; 8 write(x/10,k-1); 9 putchar(x%10+‘0‘); 10 }11 void rid1(){12 for(int i=0;i<=99;i++){13 a[i]=a[i]*2+d,d=0;14 if(a[i]>=mod){15 d+=a[i]/mod;16 a[i]%=mod;17 }18 }19 d=0;20 }21 int rid2(){22 for(int i=0;i<=99;i++)23 for(int j=0;j<=99;j++)24 c[i+j]+=a[i]*b[j];25 for(int i=0;i<=99;i++) a[i]=c[i]%mod,c[i+1]+=c[i]/mod,c[i]=0;26 }27 int main(){28 scanf("%d",&p);29 printf("%d\n",(int)(log10(2)*p+1));30 a[0]++;31 if(p>s){32 for(int i=1;i<=s;i++) rid1();33 for(int i=0;i<=99;i++) b[i]=a[i];34 p-=s;35 while(p>s) rid2(),p-=s; 36 }37 for(int i=1;i<=p;i++) rid1();38 a[0]--;39 for(int i=99,j=1;i>=0;i--,j++){40 write(a[i],5);41 if(j%10==0) putchar(‘\n‘);42 }43 return 0;44 }
不打快速幂是门美德，然而。。。
时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold
题目描述 Description
形如2P-1的素数称为麦森数, 这时P一定也是个素数. 但反过来不一定, 即如果P是个素数, 2P-1不一定也是素数. 在1998年底, 人们找到了37个麦森数. 当时最大的一个是P=3021377, 它有909526位. 但是截止到2013年2月, 美国中央密苏里大学数学家库珀领导的研究小组通过参加一个名为“互联网梅森素数大搜索”(GIMPS)项目, 日前发现了第48个梅森素数——P=57885161; 该素数也是目前已知的最大素数, 有17425170位. 如果用普通字号将它连续打印下来, 它的长度可超过65公里! 美国数学学会发言人布林说:“超大素数令数学家和计算机科学家感到兴奋.” 他认为这是素数探究的一项重大突破. 麦森数有许多重要应用, 它与完全数密切相关. 所以, 给出一个P, 请计算出2P-1.
输入描述 Input Description
一个整数P.
输出描述 Output Description
第一行: 十进制高精度数2P-1的位数.
第2-21行: 十进制高精度数2P-1的最后1000位数字. (每行输出1000位, 共输出20行, 不足1000位时高位补0)
样例输入 Sample Input
1279
样例输出 Sample Output
3860000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010407932194664399081925240327364085538615262247266704805319112350403608059673360298012239441732324184842421613954281007791383566248323464908139906605677320762924129509389220345773183349661583550472959420547689811211693677147548478866962501384438260291732348885311160828538416585028255604666224831890918801847068222203140521026698435488732958028878050869736186900714720710555703168729087
数据范围及提示 Data Size & Hint
1000≤P<2147483647
我。。。我服。
思路：某种数学公式+高精+快速幂
代码实现：
1 #include<cmath> 2 #include<cstdio> 3 #define mod 100000 4 int p,s=1650; 5 long long a[300],b[300],c[300],d; 6 void write(long long x,int k){ 7 if(!k) return; 8 write(x/10,k-1); 9 putchar(x%10+‘0‘); 10 }11 void rid1(){12 for(int i=0;i<=199;i++)13 for(int j=0;i+j<=199;j++){14 c[i+j]+=a[i]*b[j];15 if(c[i+j]>=mod){16 c[i+j+1]+=c[i+j]/mod;17 c[i+j]%=mod;18 }19 }20 for(int i=0;i<=199;i++) a[i]=c[i],c[i]=0;21 }22 void rid2(){23 for(int i=0;i<=199;i++)24 for(int j=0;i+j<=199;j++){25 c[i+j]+=b[i]*b[j];26 if(c[i+j]>=mod){27 c[i+j+1]+=c[i+j]/mod;28 c[i+j]%=mod;29 }30 }31 for(int i=0;i<=199;i++) b[i]=c[i],c[i]=0;32 }33 int main(){34 scanf("%d",&p);35 printf("%d\n",(int)(log10(2)*p+1));36 a[0]=1,b[0]=2;37 while(p){38 if(p&1) rid1();39 rid2();40 p=p>>1;41 }42 a[0]--;43 for(int i=199,j=1;i>=0;i--,j++){44 write(a[i],5);45 if(j%10==0) putchar(‘\n‘);46 }47 return 0;48 }
题目来源：洛谷,CODE[VS]
麦森数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。