【9704】&&【9109】麦森数

Time Limit: 3 second
Memory Limit: 2 MB

【问题描述】

形如2^p－1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2^p-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P＝3 021 377，它有909 526位。麦森数有许多重要应用，它与安全数密切相关。
任务：输入P（1000〈P〈3 100 000），计算2^P－1的位数和最后500位数字（用十进制高精度数表示）。不必验证2^p－1与P是否为素数。

【输入格式】

仅一行，只包含一个整数P（1000〈P〈3 100 000）。

【输出格式】

第一行：十进制高度精数2^p-1的位数。
第2-11行：十进制高度精数2^p-1的最后500位数字（每行输出50位，共输出10行，不足500位时高位补0）。

【输入样例】

1279

【输出样例】

    386

    00000000000000000000000000000000000000000000000000
    00000000000000000000000000000000000000000000000000
    00000000000000104079321946643990819252403273640855
    38615262247266704805319112350403608059673360298012
    23944173232418484242161395428100779138356624832346
    49081399066056773207629241295093892203457731833496
    61583550472959420547689811211693677147548478866962
    50138443826029173234888531116082853841658502825560
    46662248318909188018470682222031405210266984354887
    32958028878050869736186900714720710555703168729087

【题解】

p的位数比较大。不能直接用高精度强乘。需要用到快速幂。

首先介绍一下原理。

eg:2^17

我们首先把17/2->8;

然后8/2 = 4

4/2 = 2

2/2 =1

1/2 = 0;

然后组合成((((2^0*2 )^2)^2)^2)^2*2。

这样看可能有点复杂。可以看下这个程序的过程

a最初为1

void kk (int x)

{
if (x == 0) return;

kk( x /2)

a*a;

if (x 为奇数)

a*2;
}

然后把a换成一个数组就好了即用来做高精度的数组.

还记得高精度乘法的两层for循环吗,a[i+j-1] += a[i] * a[j];

然后只要记录500位就好了。我们可以不用管位数。直接500位地存，不管是2位还是25或250位都看做500位数字进行进位及乘法。

最后是输出位数的问题。

我们不可能让一个几千位的数字一直做乘法。那样即使是快速幂也会超时。

可以从数学角度考虑这个问题。

设一个数的位数为k.

比如32,k = 2;

则10^k > 32 > 10^(k-1)

然后两边取常用对数

k > lg32 >k-1;

把32换成2^n

k > n*lg2 >k-1

则k==n*lg2的整数部分+1；(因为是2^n 所以不用考虑10 100这样的数字。直接取整+1就好）

【代码】

#include <cstdio>
#include <cstring>
#include <cmath>

int p,a[600],temp[600],l = 1;

void input_data()
{
    memset(a,0,sizeof(a));
    memset(temp,0,sizeof(temp));
    scanf("%d",&p); //输入一个整数p
    a[1] = 1; //a一开始等于1，表示2^0
}

void get_ans(int now)
{
    if ( now == 0)
        return;
    get_ans(now / 2); //不断划分
    for (int i = 1;i <=500;i++)//直接取500位就可以了
        temp[i] = 0;
    for (int i = 1;i <= 500;i++)
        for (int j = 1;j <= 500;j++) //高精度乘法
            temp[i+j-1] += a[i] * a[j];
    int x = 0; //用来进位
    for (int i = 1;i <= 500;i++) //处理进位的问题
        {
            temp[i] += x;
            x = temp[i] / 10;
            temp[i] = temp[i] % 10;
        }
    if ( (now % 2 == 1)) //如果now是一个奇数 那么就要多乘一个2
        {
            for (int i = 1;i <= 500;i++)
                temp[i] = temp[i] * 2;
            x = 0;
            for (int i = 1;i <= 500;i++) //同样要再处理一次进位问题
                {
                    temp[i] += x;
                    x = temp[i] / 10;
                    temp[i] = temp[i] % 10;
                }

        }
    for (int i = 1;i <= 500;i++) //把temp再赋值给a数组
        a[i] = temp[i];
}

void output_ans() //输出答案
{
    printf("%d
",int(p*log10(2)) + 1);
    a[1] = a[1]-1; //做完了乘法还要-1才是麦森数
    for (int i = 1;i <= 500;i++) //减掉1后还要处理进位问题。（但其实这步可以省略，因为2^n，个位上的数字减去1后不可能小于0）；
        {
            if (a[i] < 0)
                {
                    a[i] +=10;
                    a[i+1]--;
                }
        }
    int tt = 0;
    for (int i = 500;i >=1;i--) //50个数字一行。
        {
            printf("%d",a[i]);
            tt++;
            if (tt == 50)
                {
                    tt = 0;
                    printf("
");
                }
        }
}

int main()
{
    input_data();
    get_ans(p);
    output_ans();
    return 0;
}