UVA 11161 - Help My Brother (II)

/* I SHALL COPY PASTE ANY PART OF MY CODE BUT SHALL REVISE && REVISE */
          /* I SHALL WRITE IT DOWN BEFORE WRITTING IT */
#include<bits/stdc++.h>
#include<cstring>
using namespace std;

#define nl printf("\n")
#define P(a) printf("%lld\n",a)
#define SP(a) printf("%lld ",a)
#define G(a) scanf("%lld",&a)
#define DB printf("I WAS HERE\n")
#define M 1505
long long fib[1550][500],i,j,k,carry,x,sz[1550];
long long last[1550][500],szlast[1550];
void bigfibo()
{
    fib[0][0]=0;
    fib[1][0]=1;
    fib[2][0]=2;
    sz[0]=1;
    sz[1]=1;
    sz[2]=1;
    long long l,i,j;
    i=3;
    while(i<=M)
        {
             carry=0;
            l=sz[i-1];
            j=0;
            while(j<l)
            {
                x=fib[i-1][j]+fib[i-2][j]+carry;
                if(x>9)
                {
                    x=x%10;
                    carry=1;
                }
                else carry=0;
                fib[i][j]=x;

                j++;

            }
            if(carry>0)
            {
                fib[i][j]=carry;
                carry=0;
                j++;
            }
            sz[i]=j;
           i++;
        }
}
void lastfibono()
{
    last[1][0]=1;
    last[2][0]=3;
    last[3][0]=6;
    szlast[1]=1;
    szlast[2]=1;
    szlast[3]=1;
    long long l,i,j,carry=0,x,val;
    i=4;

    while(i<=M)
    {
        carry=0;
        val=0;
        j=0;
        l=max(szlast[i-1],sz[i]);

        while(j<l)
        {
            val=last[i-1][j]+fib[i][j]+carry;

            if(val>9)
            {
            carry=1;
            val=val%10;
            }
            else
                carry=0;
                last[i][j]=val;

            j++;
        }
            if(carry>0)
            {
                last[i][j]=carry;
                carry=0;
                j++;
            }
            szlast[i]=j;
            i++;
    }
}
main()
{
   bigfibo();
   lastfibono();
   long long int n,tc=1;
   while(cin>>n)
   {
       if(n==0) break;
       if(n==1)
       {
           printf("Set %lld:\n",tc);
           tc++;
           printf("0\n");
           continue;
       }
       n--;
       long long div[500]={0},a[500]={0},szdiv=0,l=0,k1=0;

       long long p=n;
           l=sz[p];
           if(fib[p][0]%2==1)
           {
               j=0;
               carry=1;
               while(j<l)
               {
                   x=fib[p][j]+carry;
                   if(x>9)
                   {
                       carry=1;
                       x=x%10;
                   }
                   else carry=0;

                   a[j]=x;
                   j++;
               }
               if(carry>0)
               {
                   a[j]=carry;
                   carry=0;
                   j++;
               }
               carry=0;
               k1=0;
               for(k=j-1;k>=0;k--)
               {
                   a[k]+=(carry*10);
                   if(a[k]>=2)
                   {
                       x=a[k]/2;
                       carry=a[k]%2;
                       div[k1]=x;
                       k1++;

                   }
                   else if(k1>0)
                   {
                       div[k1]=0;carry=a[k];
                       //SP(div[k1]);
                       k1++;
                   }
                   else
                    carry=a[k];

               }
               szdiv=k1;
           }
           else
           {
               carry=0;
               k1=0;
               for(k=l-1;k>=0;k--)
               {
                   a[k]=fib[p][k];
               }
               for(k=l-1;k>=0;k--)
               {
                   a[k]+=(carry*10);
                   if(a[k]>=2)
                   {
                       x=a[k]/2;
                       carry=a[k]%2;
                       div[k1]=x;
                       k1++;
                   }
                else if(k1>0)
                   {
                       div[k1]=0;carry=a[k];
                       k1++;
                   }
                   else
                    carry=a[k];
               }
               szdiv=k1;
           }
            long long k2=0;
            long long sum[500]={0};
           for(i=szdiv-1;i>=0;i--)
           {
               sum[k2]=div[i];k2++;
           }
       long long x,ii=max(szlast[n-1],szdiv),output[500]={0};
       j=0;
       carry=0;
        while(j<ii)
            {
                x=last[n-1][j]+sum[j]+carry;
                if(x>9)
                {
                    x=x%10;
                    carry=1;
                }
                else
                    carry=0;
                output[j]=x;
                j++;
            }
            if(carry>0)
            {
                output[j]=carry;
                carry=0;
                j++;
            }
            printf("Set %lld:\n",tc);
           tc++;
            for(i=j-1;i>=0;i--)
            {
                printf("%lld",output[i]);
            }
            nl;
   }

}