问题标题: 洛谷：P1045 麦森数

思路：

首先可以想见，就算快速幂+压位，对于3100000这个数来说，完全算出准确值是很不靠谱的事情（空间允许，时间不允许）

所以，算位数是一个纯粹数学问题。

算位数么，肯定能想到的是log(10,2^n)

2^n很大，那就变形处理，变成n*log(10,2)

log(10,2)是一个常数，你可以找电脑里的计算器算，多保留几位小数放进去，也可以这样：

uses math;//math库里有算log的函数

log10(2);或者logn(10,2);

——看哪个还敢说pascal里没算log的函数，自己不去好好学习RTL。

最后要输出的是writeln(trunc(n*log10(2))+1);

用trunc直接截去尾部，不要小数，然后加一个1补偿一下，用round()会导致一些不好调整的混乱。

然后我们开始算吧。

首先是知道什么叫快速幂。

所谓快速幂，写成一个式子就很直观了——

(63)10=(111111)2

2^63 = 2^32 * 2^16 * 2^8 * 2^4 * 2^2 * 2^1

而2^32=(2^16)^2，不需要连乘32个2，只要使用前面的结果就行。

用快速幂，这个例子上只需10次乘法，用暴力方法，你需要做63次，当数更大的时候，效率优势是更加明显的

(48)10=(110000)2

2^48 = 2^32 * 2^16

（这其实是一种分治法思想）

接下来的问题变成了，我如何知道那些二进制位上是1.

选择很多，你可以从数据可能的最高位开始往下减，记录一下那些对应的二进制位

当然也可以从最低位开始看。

要说从最低位开始看，强烈建议一下树状数组中用的一个位运算方法——lowbit。

Lowbit的作用是返回2^（二进制表示的i的末尾0的个数）

典型方法是不断mod 2^i，直到有余数为止。一种巧妙的运算方法是 i and (-i)。

因为正二进制数取反以后再加一，就得到了负的此数，而末尾0的个数一样，所以只需要and运算就可以取到最后所有的0和第一个1。

以下以48为例。

48 00110000

-48    11010000(11001111+1)
48 and (-48)    00010000
lowbit(48)=16
48-lowbit(48)=32
lowbit(32)=32
32-lowbit(32)=0

好了，到此为止我们知道了，48这个数在表示2^4和2^5的二进制位上是1.那2^48只需2^(2^4) * 2^(2^5)就行

63等其他数同理，大家可以自己推推看。

之所以要详细说从低位往高位看，是因为——

算2^32前要算2^16,算2^16前算2^8,.....最后要先知道2^1,然后才能一个个往上推。

那这样，一路往上推2^(2^i)的过程中，等到算出我们需要的2^(2^i)的值的时候可以直接乘到结果里去了。

一开始我们考量过，1s算出每个准确数字并不靠谱，题目只是要求输出最后的500位，那我在计算的时候只需要保留最后的500位，更高位的计算我可以选择根本就不做。

这样的话，我需要3个高精度数组（压不压位随你便，影响并不大，最多就是内存开的再小一点，复制数组的时间代价更小）

第一个存2^(2^times),第二个存最后输出的结果，第三个作为计算过程中临时存放结果的数组（两数组相乘，在算完前结果覆盖回任何一个乘数数组都会出事的）。

while (n>0)
{
    while (times<lowbit(n))
   {

对第一个数组平方，同时更新一下times标记（times*2，表示平方了一下）

} 把第一个数组（2^(2^times)）乘第二个数组（结果），存回第二个数组（结果）

dec(n,lowbit(n));//自己看看二进制表示，想想为什么，这个比较直观的

} 最后别忘了减一、退位处理（其实想想就知道，不可能退位，怕出事情，退位写那里也没事）和按要求输出结果。

具体的高精度乘法、减法的实现这里不做讲解，这是一个基本能力问题。

还有一点，能递推的最好不要写递归了，这个题目上写递归，协调起来真的灾难的很。