麦森数解题报告

《麦森数解题报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、{先用2^24为一次来优化，再用2^(pdiv2)*2(pdiv2)高精度当p为奇数时用2^(pdiv2)*2(pdiv2)*2}varp,q,f,i,j,x,t,l,k,n:longint;s:int64;a,b,c:array[1..1001]oflongint;procedurefb;{高精度乘法高*高}vari,j:integer;beginfori:=1toldoforj:=1toldobeginb[i+j-1]:=b[i+j-1]+a[i]*a[j];b[i+j]:=b[i+j]+b[i+j-1]div10;b[i+j-1]

2、:=b[i+j-1]mod10;end;ifi+j-1>=500thenl:=500elseifb[i+j]>0thenl:=i+jelsel:=i+j-1;{l记录最高位}f:=2{f判断，f=2则记录在b数组中}end;procedurefa;vari:integer;beginfb;{2^(pdiv2)*2(pdiv2)}fori:=1toldobeginc[i]:=c[i]+b[i]*2;c[i+1]:=c[i]div10;c[i]:=c[i]mod10;end;{高精度*单精度}f:=1;{f=1则记录在c数组中}end;pr

3、oceduref1;beginfori:=1to(pmod48)div2do{24的余数}begint:=0;forj:=1toldobegina[j]:=a[j]*2+t;t:=a[j]div10;{t：储存a[j]div10,并赋值给下一个a[j]}a[j]:=a[j]mod10;end;{高精度*单精度}a[l+1]:=t;if(a[l+1]>0)and(l<500)theninc(l);{l：记录最高位，当l到500时不再往上计算}end;end;proceduref24;begina[1]:=1;l:=1;fori:=1top

4、div48dobeginforj:=1toldobegina[j]:=a[j]*16777216+t;{16777216=2^24}t:=a[j]div10;a[j]:=a[j]mod10;end;{一次*2^24}k:=l;whilet>0dobegininc(k);x:=a[k]+tmod10;t:=tdiv10+xdiv10;a[k]:=xmod10;end;{把t的值一位位的放入a[k],k=l+1,l+2……}ifk<500thenl:=kelsel:=500;{l：当l到500时不再往上计算}end;end;beginass

5、ign(input,'Mason.in');reset(input);assign(output,'Mason.out');rewrite(output);read(p);n:=8;{n：记总位数}f24;{以2^24为一次运算（减少O）}f1;{以2为一次运算解决p/24的余数}ifodd(p)thenfa{做2^(pdiv2)*2(pdiv2)*2}elsefb;{做2^(pdiv2)*2(pdiv2)}{判断p的奇偶}iff=1thenfori:=1to500dob[i]:=c[i];{当记录在c数组时，把c赋值给b}dec(b[

6、1]);{b[1]-1}i:=1;while(b[i]<0)dobegindec(b[i+1]);b[i]:=b[i]+10;i:=i+1;end;{做-1}{开始算位数}s:=1;{模拟2^p-1的前几位}forq:=1topdiv11dobegins:=s*2048;{先一次*2048来优化程序}whiles>100000000do{当s>10^8时，n加一位，s去除末位，以防超出数据结构}{原先的n=8：10^8为8位}beginn:=n+1;{n：记录总位数}s:=sdiv10;end;end;forq:=1topmod11do

7、{一次*2来做剩余的}begins:=s*2;whiles>100000000dobeginn:=n+1;s:=sdiv10;end;end;write(n);{输出总位数}fori:=500downto1dobeginifimod50=0thenwriteln;write(b[i]);end;{输出500位}close(input);close(output);end.