学步园

题目分析：http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1142

#include<iostream>
#include<cstdio>
using namespace std;
struct node{
   __int64 num,sum;
   int  flag;
}arr[10000020];
int main()
{
   int a,b;
   __int64 num,sum;
   for(int i=1;i<1000010;i++)
	   arr[i].flag=0;

   arr[1].flag=true;
   arr[1].num=1;
   arr[1].sum=0;
   while(scanf("%d %d",&a,&b)!=EOF)
   {
	   for(int i=a;i<=b;i++)
	   {
		   __int64 n=i;
		   sum=0;
		   num=n;
		   while(n!=1)
		   {
			   if(n<1000010&& arr[n].flag==1)
			   {
				   sum+=arr[n].sum;
				   if(arr[n].num>num)
					     num=arr[n].num;
				   break;
			   }
			   else
			   {
				   if(n%2==0)
				       n/=2;
			       else
			      {
				     n=3*n+1;
				    if(n>num)
					    num=n;
			       }
			       sum++;
			   }
		   }//****for
		   arr[i].num=num;
		   arr[i].sum=sum;
		   arr[i].flag=1;
	   }
	   num=0,sum=0;
	   for(int i=a;i<=b;i++)
	   {
		   if(arr[i].num>num)
			   num=arr[i].num;
		   sum+=arr[i].sum;
	   }
	   printf("%I64d %I64d\n",sum,num);
   }

   //system("pause");
   return 0;
}