OpenJudge 2706 麦森数

链接地址：http://bailian.openjudge.cn/practice/2706/

题目：

总时间限制:

1000ms

内存限制:

65536kB

描述

形如2^p-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数。2^p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。
任务：从文件中输入P (1000<P<3100000) ,计算2^p-1的位数和最后500位数字（用十进制高精度数表示）

输入

文件中只包含一个整数P(1000<P<3100000)

输出

第1行：十进制高精度数2^p-1的位数。
第2-11行：十进制高精度数2^p-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）
不必验证2^p-1与P是否为素数。

样例输入

1279

样例输出

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

来源

联赛复赛试题2003

思路：

这题自己写的方法超时了，参考了《程序设计引导及在线实践》的思路

代码：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>


#define LEN 125

void mul4(int *a,int *b)
{
    int c[LEN];
    int temp;
    memset(c,0,sizeof(int)*LEN);
    for(int i = 0; i < LEN; i++)
    {
        temp = 0;
        for(int j = 0; j < LEN; j++)
        {
            if(i + j >= LEN) break;
            c[i + j] += a[i] * b[j] + temp;
            temp = c[i + j] / 10000;
            c[i + j] = c[i + j] % 10000;
        }
    }
    memcpy(a,c,LEN * sizeof(int));
}

int main()
{
    int a[LEN],b[LEN];
    int i,j;
    memset(a,0,sizeof(int)*LEN);
    memset(b,0,sizeof(int)*LEN);
    b[0] = 2; a[0] = 1;
    int p;
    scanf("%d",&p);
    printf("%d
",(int)(p * log10(2)) + 1);
    while(p)
    {
        if(p & 1)
        {
            mul4(a,b);
        }
        p >>= 1;
        mul4(b,b);
    }
    a[0]--;

    char out_str[LEN * 4 + 1];
    for(i = 0; i < LEN; i++)
    {
        sprintf(&out_str[i*4],"%04d",a[LEN-1-i]);
    }

    for(i = 0;i < 10; i++)
    {
        for(j = 0; j < 50; j++)
        {
            printf("%c",out_str[i*50+j]);
        }
        printf("
");
    }
    return 0;
}