记录编号	35415	评测结果	AAAAAAAAAA
题目名称	失落的神庙	最终得分	100
用户昵称	Citron酱	是否通过	通过
代码语言	C++	运行时间	0.037 s
提交时间	2012-02-21 20:40:34	内存使用	19.34 MiB

#include <fstream>

#define I_F "losttemple.in"
#define O_F "losttemple.out"

const long long P=5000000;

struct lb
{
	long long x,y;
	lb *next;
}*s[P]={NULL};
long long n, ans;

void Input();
long long Search(const long long);
void Output();

int main()
{
	Input();
	ans=Search(n);
	Output();
	return 0;
}

void Input()
{
	std::ifstream fin(I_F);
	fin>>n;
	fin.close();
	
	s[0]=new lb;		s[1]=new lb;
	s[0]->x=0;			s[1]->x=1;
	s[0]->y=1;			s[1]->y=1;
	s[0]->next=NULL;	s[1]->next=NULL;
}

long long Search(const long long x)
{
	for (lb *i=s[x%P]; i!=NULL; i=i->next)
		if (i->x==x)
			return i->y;
	
	if (s[x%P]==NULL)
	{
		s[x%P]=new lb;
		s[x%P]->x=x;
		s[x%P]->next=NULL;
		s[x%P]->y=Search(x/2)+Search(x/3)+Search(x/5)+Search(x/7);
		return s[x%P]->y;
	}
	lb *i=s[x%P];
	while (i->next!=NULL)
		i=i->next;
	i->next=new lb;
	i=i->next;
	i->x=x;
	i->next=NULL;
	i->y=Search(x/2)+Search(x/3)+Search(x/5)+Search(x/7);
	return i->y;
}

void Output()
{
	std::ofstream fout(O_F);
	fout<<ans<<std::endl;
	fout.close();
}