记录编号	26603	评测结果	AAAAAAAAAA
题目名称	失落的神庙	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.431 s
提交时间	2011-07-25 15:12:56	内存使用	2.56 MiB

#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>

using namespace std;

long long n;

struct node
{
	long long l,r,v;
}q2[20001],q3[20001],q5[20001],q7[20001],q0[20001];
int s0,t0,s2,s3,s5,s7,t2,t3,t5,t7;
void solve()
{
	scanf("%lld",&n);
	if (n==1 || n==0) {printf("1\n");return;}
	q2[1].l=q3[1].l=q5[1].l=q7[1].l=2;
	q2[1].r=3;q3[1].r=5;q5[1].r=9;q7[1].r=13;
	q2[1].v=1;q3[1].v=1;q5[1].v=1;q7[1].v=1;
	s0=s2=s3=s5=s7=t2=t3=t5=t7=1;
	t0=0;
	while (s2<=t2 && s3<=t3 && s5<=t5 && s7<=t7)
	{
		long long R=min(min(q2[s2].r,q3[s3].r),min(q5[s5].r,q7[s7].r));
		long long L=q2[s2].l;
		
		q0[++t0].l=L;q0[t0].r=R;
		q0[t0].v=q2[s2].v+q3[s3].v+q5[s5].v+q7[s7].v;
		
		if (L*2<=n)
		{
			q2[++t2].l=L*2;q2[t2].r=min(R*2+1,n);q2[t2].v=q0[t0].v;
		}
		if (L*3<=n)
		{
			q3[++t3].l=L*3;q3[t3].r=min(R*3+2,n);q3[t3].v=q0[t0].v;
		}
		if (L*5<=n)
		{
			q5[++t5].l=L*5;q5[t5].r=min(R*5+4,n);q5[t5].v=q0[t0].v;
		}
		if (L*7<=n)
		{
			q7[++t7].l=L*7;q7[t7].r=min(R*7+6,n);q7[t7].v=q0[t0].v;
		}
		
		q2[s2].l=R+1;   if(R+1>q2[s2].r) s2++;
		q3[s3].l=R+1;   if(R+1>q3[s3].r) s3++;
		q5[s5].l=R+1;   if(R+1>q5[s5].r) s5++;
		q5[s7].l=R+1;   if(R+1>q7[s7].r) s7++;
	}
	
	printf("%lld\n",q0[t0].v);
	
}

int main()
{
	freopen("losttemple.in","r",stdin);
	freopen("losttemple.out","w",stdout);
	solve();
	return 0;
}