洛谷 P1045 麦森数

2019-11-08 01:02:07

字体：大中小

来源：转载

供稿：网友

题目

形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。

任务：从文件中输入P（1000

题解

计算2的p次方，令m=p/2，则有两种情况：如果p是偶数，那么2p=(2m)2，否则有2p=2(2m)2，基于这种思想，则有算法EXPREC的递归算法。计算完后，输出2p的位数，计算方法 trunc(ln(2)/ln(10)*n)+1 最后输出2p的最后500位

代码

var n,x,y:longint; a,b,c:array[1..500*3]of longint;procedure mul;var i,j,g:longint;begin for i:=1 to 500 do begin g:=0; for j:=1 to 500 do begin c[i+j-1]:=c[i+j-1]+a[i]*a[j]+g; g:=c[i+j-1] div 10; c[i+j-1]:=c[i+j-1] mod 10; end; c[i+j]:=g; end;end;procedure mul2;var s,g,i,j:longint;begin for i:=1 to 500 do begin g:=0; for j:=1 to 500 do begin c[i+j-1]:=c[i+j-1]+a[i]*b[j]+g; g:=c[i+j-1] div 10; c[i+j-1]:=c[i+j-1] mod 10; end; c[i+j]:=g; end;end;procedure exprec(m:longint);begin if m=0 then c[1]:=1 else begin exprec(m div 2); a:=c; fillchar(c,sizeof(c),0); if odd(m) then mul2 else mul; end;end;begin readln(n); b[1]:=2;x:=1; exprec(n); writeln(trunc(ln(2)/ln(10)*n)+1); c[1]:=c[1]-1; for y:=500 downto 1 do begin write(c[y]); if x mod 50=0 then writeln; inc(x); end;end.

上一篇：洛谷 P1048 采药

下一篇：学习笔记1-basic应用模板目录结构