记录编号	192106	评测结果	AAAAAAAAAA
题目名称	[NOIP 2003]麦森数	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	1.419 s
提交时间	2015-10-09 19:44:59	内存使用	0.28 MiB

/*提示 
l第一问是很简单的，只需要求一个对数而已，数学原理：十进制正整数n的位数为int(log10(n))+1。所以2^P-1的位数int(log10(2)^p)+1 = int(p*log10(2))+1 。 
l即int(p*(ln2/ln10))+1 
l本题的解题方法很多，其中分治也是一种巧妙的方法。首先可以想到： 
  2n=(2 n div 2)2*2 (n mod 2) ，即：如果要计算2n，就要先算出2 n div 2，然后用高精度乘法算它的平方，如果n是奇数还要再乘以2，写成递归公式就是：f(n)=(f(n div 2))2*2(n mod 2)。 
当然，递归是要有边界值的，这就是当n=0时，f(n)=1。还要补充一点，该数的长度是可以用公式计算的，所以在做高精度乘法时，只要取最后500位运算就行了。*/
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <string>
#include <cstring>
#include <cstdio>
#include <fstream>
  
using namespace std;
 
string num;
char s[10];
int p, w = 0, g[129] = {0}, nw = 1;
inline void gaojing(); 
 
main()
{
	freopen("mason.in", "r", stdin);
	freopen("mason.out", "w", stdout);
	int i;
	g[1] = 1;
	cin >> p;
	for (i = 1; i <= p; i++)
		gaojing();
	--g[1];
	w = (p * (log(2) / log(10))) + 1;
	printf("%d\n", w);
	g[63] %= 10000;
	sprintf(s, "%04d", g[63]);
	num += s;
	for (i = 62; i > 0; i--){
		sprintf(s, "%08d", g[i]);
		num += s;
	}
	for (int i = 0; i < 500; i++){
		cout << num[i];
		if(i==49||i==99||i==149||i==199||i==249||i ==299||i==349||i==399||i==449||i==499)
		    cout << endl;
	}
	fclose(stdin);
	fclose(stdout);
//	for (; ; );
}
 
 
inline void gaojing(){
	int i = 1, x = 0;
	while (i <= min(63, nw + 5)){
		g[i] = x + g[i] * 2;
		x = g[i] / 100000000;
		g[i] %= 100000000;
		i++;
		if (i > nw && g[i] != 0)
			nw++;
	}
	x = 0;
}