题目描述

 形如 2^P−1 的素数称为麦森数，这时 P 一定也是个素数。但反过来不一定，即如果 P 是个素数，2P−1 不一定也是素数。到 1998 年底，人们已找到了 37 个麦森数。最大的一个是 P=3021377，它有 909526 位。麦森数有许多重要应用，它与完全数密切相关。

任务：输入 P(1000<P<3100000)，计算 2P−1 的位数和最后 500 位数字（用十进制高精度数表示）

输入

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

输出

 第一行：十进制高精度数 2P−1 的位数。

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

不必验证 2P−1 与 P 是否为素数。(正好偷个懒~)

输入输出样例

输入：1279

输出：

386
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000104079321946643990819252403273640855
38615262247266704805319112350403608059673360298012
23944173232418484242161395428100779138356624832346
49081399066056773207629241295093892203457731833496
61583550472959420547689811211693677147548478866962
50138443826029173234888531116082853841658502825560
46662248318909188018470682222031405210266984354887
32958028878050869736186900714720710555703168729087

思路:

都这么长了，高精妥妥的

再加上个快速幂，难度噌噌噌上涨……

SO,我们直接来详细的分析

STEP 1:定义用于设置数组 a 的有效长度的函数 setLen 。数组 a 的第 0 个元素 a[0] 存储的是数组的有效长度。函数会从后向前遍历数组，找到第一个非零元素，并将有效长度设置为该位置。如果有效长度超过 500，则设置为 500

STEP 2:定义用于将数组 b 的内容复制到数组 a 中的函数 numCpy

STEP 3:定义大数乘法的函数Mult。其中数组 a 和 b 分别表示两个大数，数组 r 用于存储乘法的结果。函数通过逐位相乘并处理进位来计算结果，最后调用 setLen 和 numCpy 来更新结果数组 a。

STEP 4:定义快速幂函数。它通过不断地平方 a 并根据 b 的二进制位来决定是否将当前的 a 乘到结果 r 中，从而高效地计算 a ^​​​​​​ b 。

STEP 5:计算并输出 2^p 的位数，公式为 floor(p * log10(2)) + 1。

STEP 6:调用 fastpow 计算 2^p，结果存储在 r 中。

STEP 7:将 r[1] 减 1，得到 2^p−1。

STEP 8:从高位到低位输出结果，每行输出 50 位。

代码

#include<bits/stdc++.h>
using namespace std;
void setLen(int *a,int i)
{
    while(a[i]==0&&i>1)
    {
        i--;
    }
    if(i>=500)
    {
    	i=500;
	}
    a[0]=i;
}
void numCpy(int *a,int *b)
{
    for(int i=0;i<=b[0];i++)
    {
        a[i]=b[i];
    }
}
void Mult(int *a,int *b)
{
	int r[1005];
	memset(r,0,sizeof(r));
    for(int i=1;i<=a[0];i++)
    {
        int c=0;
        for(int j=1;j<=b[0];j++)
        {
            r[i+j-1]+=a[i]*b[j]+c;
            c=r[i+j-1]/10;
            r[i+j-1]%=10;
        }
        r[i+b[0]]+=c;
    }
    setLen(r,a[0]+b[0]);
    numCpy(a,r);
}
void fastpow(int *a,int b,int *r)
{
    while(b>0)
    {
        if(b%2==1)
        {
            Mult(r,a);
        }
        Mult(a,a);
        b/=2;
    }
}
int main()
{
    int p,r[1005]={1,1},a[1005]={1,2};
    cin>>p;
    cout<<int(floor(p*log10(2)))+1<<"\n";
    fastpow(a,p,r);
    r[1]--;
    for(int i=500;i>0;i--)
    {
    	cout<<r[i];
    	if(i%50==1)
    	{
    		cout<<'\n';
		}
	}
    return 0;
}

运行结果