麦森数--NOIP2003

题目描述

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

任务：从文件中输入PPP （1000<P<31000001000<P<31000001000<P<3100000 ），计算2P−12^{P}-12P−1 的位数和最后500位数字（用十进制高精度数表示）

输入输出格式

输入格式：

文件中只包含一个整数PPP （1000<P<31000001000<P<31000001000<P<3100000 ）

输出格式：

第一行：十进制高精度数2P−12^{P}-12P−1 的位数。

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

不必验证2P−12^{P}-12P−1 与P 是否为素数。

高精+快速幂

#include<cstdio>

#include<math.h>

#include<string.h>

#include<iostream>

using namespace std;

int P;

double n;

int a[110000],ans[110000];

void read(int &x)  //快读

{

	int f=1;

	char t=getchar();

	x=0;

	while((t<48)or(t>57))

	{

		if(t=='-')f=-1;

		t=getchar();

	}

	while((t>=48)and(t<=57))

	{

		x=x*10+t-48;

		t=getchar();

	}

	x*=f;

}

void jian(int a[])

{

	a[1]-=1;

	for (int i=1; i<=a[0]; ++i)

	{

		if (a[i]<0)

		{

			a[i]+=10;

			--a[i+1];

		}

		else break;

	}

}

void cheng(int a[])

{

	int len=a[0]+1;

	int c[510];

	memset(c,0,sizeof(c));

	for (int i=1; i<=a[0]; ++i)

	{

		int t=0;

		c[i]=c[i]+t+a[i]*2;

		t=c[i]/10;

		c[i]%=10;

		c[i+1]=t;

	}

	while ((c[len]==0) && (len>1)) --len;

	for (int i=1; i<=len; ++i) a[i]=c[i];

	a[0]=len;

}

void cheng1(int a[],int b[])

{

	int c[110000];

	memset(c,0,sizeof(c));

	int n=min(a[0],500),m=min(b[0],500),len=n+m;

	for (int i=1; i<=n; ++i)

	{

		int t=0;

		for (int j=1; j<=m; ++j)

		{

			c[i+j-1]=c[i+j-1]+t+a[i]*b[j];

			t=c[i+j-1]/10;

			c[i+j-1]%=10;

		}

		c[i+m]=t;

	}

	while ((c[len]==0) && (len>1)) --len;

	for (int i=1; i<=len; ++i) a[i]=c[i];

	a[0]=len;

}

int main()

{

	//freopen("mason.in","r",stdin);

	//freopen("mason.out","w",stdout);

	read(P);

	n=(double)P*(double)(log(2)/log(10));//直接算位数

	n+=1;

	printf("%d",(int)n);

	a[1]=2;

	a[0]=1;

	ans[1]=1;

	ans[0]=1;

	for (; P; P>>=1,cheng1(a,a))  //p>>=1 等于 p /= 2,cheng1(a,a)为预处理,为cheng1(ans,a)做准备

		if (P&1) cheng1(ans,a);  //是奇数还要再乘一个

	jian(ans);

	for (int i=500; i>=1; --i)

	{

		if (i%50==0) printf("\n");

		printf("%d",ans[i]);

	}

	return 0;

}