记录编号	35737	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2012-03-01 20:17:25	内存使用	0.26 MiB

#include <cstdio>
#include <cmath>
using namespace std;
const int SIZE=1010; 
int P;

class hugeint
{
public:
    int len,num[SIZE];
	void clear()
	{
		len=0;
		for(int i=0;i<=503;i++) num[i]=0;
	}
};
hugeint two;

hugeint times(hugeint a,hugeint b)
{
    int i,j;
    hugeint ans;
    ans.clear();
    for (i=1;i<=a.len;i++)
        for (j=1;j<=b.len;j++)
            ans.num[i+j-1]+=a.num[i]*b.num[j];
    for (i=1;i<=a.len+b.len;i++)
    {
		if(i>502)
			break;
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]=ans.num[i]%10;
    }
    if (ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
	if(ans.len>502)
		ans.len=502;
    return ans;
}

int digit(int p)
{
	double ln2=log( double(2) );
	double ln10=log (double(10) );
	int digit=int(p*ln2/ln10);
	return digit+1;
}

hugeint pow(int k)
{
	hugeint tmp;
	tmp.clear();
	if(k==1) return two;
	tmp=pow(k/2);
	tmp=times(tmp,tmp);
	if(k%2==1)
		tmp=times(tmp,two);
	return tmp;
}

int main()
{
	freopen("mason.in","r",stdin);
	freopen("mason.out","w",stdout);
	scanf("%d\n",&P);
	printf("%d\n",digit(P));

	two.clear();
	two.len=1;
	two.num[1]=2;
	
	hugeint ans;
	ans.clear();
	ans=pow(P);
	ans.num[1]--;
	for (int i=500;i>=1;i--)
	{
		printf("%d",ans.num[i]);
		//if((i-1)%50==0)
			//printf("\n");
	}
	return 0;
}