Blog·Tanky WooABOUTRSS

百练oj2706 麦森数

16 May 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

/首先考虑2的p次方减1有多少位。 因为2的p次方的个位只能是2,4,6,8,所以减1后和2的p次方

位数相同。 这里可以使用double log10(double x)函数。分析为什么? 这个地方要学会分析/ /其次分析2的p次方末500位怎么求?

显然,对于任何p>0,考虑p的二进制形式,不难得到:

P = a020 + a121 + a222 + … + an-12n-1 + 2n

这里,ai要么是1,要么是0.

因而:

2p = 2a0 * 22a1 * 24a2 * 28a3 * … * 2an-12n-1 * 22n(这里给大家解释下,因为无法编辑出来,所以口头说明下:2an-12n-1是2的an-1*2n-1次方,同理22n是2的2n次方)。

这里用数组来存放大整数,数组的一个元素对应于十进制大整数的

一位。如果本题也这么做,就会超时。 为了加快计算速度,可以用一个数组元素对应于大整数的四位, 即将大整数表示为10000进制,而数组中的每一个元素就存放10000

进制数的一位。 例如:存放6373384,那么只需要2个元素就可以了,a[0] = 3384,

a[1] = 637 因为要存放500个数,而一个数组元素表示4位10进制,所以只需要

125个元素就可以了。

*/

 #include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LEN 125  //每个数组元素存放十进制的4位,因此数组最

多只要125个元素即可
/*
Multiply函数的功能是计算高精度乘法 a * b
结果的末500位放在 a 中
*/
void Multiply(int *a, int *b)
{
    int i, j;
    int nCarry; //存放进位
    int nTmp;
    int c[LEN];   //存放结果的末500位

    memset(c, 0, sizeof(int)*LEN);   //现开始写成500居

然没结果
    for(i = 0; i < LEN; i++)
    {
        nCarry = 0;
        //考虑下面为什么是LEN-i,因为 i+j < LEN,否

c会越界。
        for(j = 0; j < LEN - i; j++)  
        {
            nTmp = c[i+j] + a[j]*b[i] + 

nCarry;
            c[i+j] = nTmp % 10000;
            nCarry = nTmp / 10000;
        }
    }
    memcpy(a, c, LEN * sizeof(int));
}

int main()
{
    int i;
    int p;
    int anPow[LEN];  //存放不断增长的2的次幂
    int aResult[LEN];  //存放最终结果的末500位
    scanf("%d", &p;);
    printf("%d\n", (int)(p * log10(2.0))+1);

    //下面将2的次幂初始化为2^(2^0)
    //最终结果为1
    anPow[0] = 2;
    aResult[0] = 1;
    for(i = 1; i < LEN; i++)
    {
        anPow[i] = 0;
        aResult[i] = 0;
    }


    //下面计算2的p次方
    while(p > 0)
    {
        if(p & 1)
            Multiply(aResult, anPow);   //如果

ai的值为1,则将最终结果乘以22 i 次方
        p >>= 1;
        Multiply(anPow, anPow);   //计算2的2的

(i+1)次方,用22 i 次方乘以22 i 次方
    }

    aResult[0]--;//2的p次方算出后减1

    //输出结果
    for(i = LEN-1; i >= 0; i--)
    {
        if(i % 25 == 12)
            printf("%02d\n%02d", aResult

[i]/100, aResult[i] % 100);
        else
        {
            printf("%04d", aResult[i]);
            if(i % 25 == 0)
                printf("%\n");
        }
    }
    return 0;
}