急需麦森数详细算法分析(不需要程序）

答案:1 悬赏:0

解决时间 2021-01-14 22:07

提问者网友：浪荡绅士
2021-01-14 19:19

急需麦森数详细算法分析(不需要程序）

最佳答案

二级知识专家网友：罪歌
2021-01-14 20:09

题目要求：求2^p-1的位数和它的前五百位，已知p（1000这道题的难点在于求2的p次方。由于p的范围过大，所以要采用二分法快速求幂。即：A^p=A^(p div 2) * A(p div 2) (p为偶数)或A^p=A^(p div 2) * A(p div 2) * A (p为奇数)。把p转换为二进制的数字，存入数组B中，然后从二进制p的末位开始，ans:=1(A^0)，如果p[I]=1，ans:=ans*A；如果p[I]=0,ans:=ans*ans。
对于求2^p的位数，用换底公式即可。Log10(2^p)=p*ln(2)/ln(10)，然后加1再trunc即可。（因为10^n有n+1位，所以要加1）。
这道题要用高精度去做，我是编了两个过程，一个乘二，一个平方。刚开始是是高精度乘法忘了进位。解决了这个问题之后，又发现我又理解错了，要求最后500位，而我是把ans算到500位之后就跳出循环了。实际上只需要把ans计算到500位置后每次只计算后500位并且只保留500位即可。
在输出的时候要先判断ans的位数（lans）是否到了500位，如果没有到，则需要输出500-lans个0，并且50个换一下行，然后输出ans；如果lans>=500则直接输出并换行。
还有，别忘了把ans的末位减一！

我要举报

如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！