> #include <stdio.h>
> long long   n,num[1000001],t[10];
> 
> int  main()
> {
>      long  long i,j;
>      while (scanf ("%I64d",&n)!=EOF)
>      {
>            num[1]=1;
>            num[2]=2;
>            for (i=3;i<=n;i++)
>            {
>                if (i%2==1)    num[i]=num[i-1];
>                if (i%2==0)    num[i]=num[i-2]+num[i/2];  //dp的思想 
////////////////////////////////上面加法溢出！！！！！！！！！！！！！！
>            }
>            for (i=0;i<9;i++)
>            {
>                t[i]=num[n]%10;
>                num[n]/=10;
>            }
>            for (i=8;i>=0;i--) 
>               if (t[i])
>                   printf ("%d",t[i]);
>            printf("\n");
>      }
>      return 0;
> }