记录编号	43534	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2012-10-11 10:58:39	内存使用	3.16 MiB

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

//?n=y*log(x)/log(10)+1，x^y是一个n位数
//2^p-1与2^p位数一定一样(p>0 p:integer)

struct bint
{
    int len,num[500];
};

bint bnum1,bnum2;

bint bmul(bint a,bint b)
{
	bint c={0};
	int i,j,temp;
	for (i=0;i<a.len;i++)
		for (j=0;j<b.len;j++)
		{
			if (i+j>=500)
				break;
			c.num[i+j]+=a.num[i]*b.num[j];
		}
	c.len=a.len+b.len;
	if (c.len>500)
		c.len=500;
	temp=0;
	for (i=0;i<c.len;i++)
	{
		c.num[i]+=temp;
		temp=c.num[i]/10;
		c.num[i]%=10;
	}
	if (!c.num[c.len-1])
		c.len--;
	return(c);
}

bint bpower(bint a,int p)
{
	bint b;
	if (p==0)
		return(bnum1);
	if (p&1)
	{
		b=bpower(a,p/2);
		b=bmul(b,b);
		b=bmul(b,a);
	}
	else
	{
		b=bpower(a,p/2);
		b=bmul(b,b);
	}
	return(b);
}

int main(void)
{
	freopen("mason.in","r",stdin);
	freopen("mason.out","w",stdout);
	bnum1.num[0]=1;
	bnum1.len=1;
	bnum2.num[0]=2;
	bnum2.len=1;
	bint a;
	int i,j,p,n;
	cin>>p;
	n=int(p*log(2.0)/log(10.0)+1);
	cout<<n<<endl;
	a=bpower(bnum2,p);
	for (i=0;i<10;i++)
	{
		for (j=0;j<50;j++)
		{
			if (i==9&&j==49)
				cout<<a.num[499-(i*50+j)]-1;
			else
				cout<<a.num[499-(i*50+j)];
		}
		cout<<endl;
	}
	return(0);
}