TREENUM - Tree Num
Tác giả: hieult
Ngôn ngữ: C++
//#include <conio.h>
#include <stdio.h>
#include <string.h>
#define du 100000000
struct so
{
int scs,a[10];
};
so f[40];
void print(so A)
{
int n = A.scs;
printf("%d",A.a[n]);
for(int i = n-1;i>=1;i--)
printf("%08d",A.a[i]);
}
/* Tinh Tong */
void sum(so &tong, so b)
{
so A = tong;
if(A.scs > b.scs) for(int i = b.scs+1; i <= A.scs; i++) b.a[i] = 0;
if(b.scs > A.scs) {for(int i = A.scs+1; i <= b.scs; i++) A.a[i] = 0; tong.scs = b.scs;}
int nho = 0;
for(int i = 1; i <= tong.scs ; i++)
{
tong.a[i] = (A.a[i] + b.a[i] + nho)%du;
nho = (A.a[i] + b.a[i] + nho)/du;
//printf("%c ",a[i]);
}
if(nho > 0){ tong.scs++ ; tong.a[tong.scs] = nho ;}
}
int main()
{
unsigned long long n;
int T,t;
f[0].scs = 1;
f[0].a[1] = 1;
for(long i=1;i<=70;i++)
{
int nho = 0;
f[i].scs = f[i-1].scs;
for(int j = 1;j<=f[i].scs;j++)
{
f[i].a[j] = (f[i-1].a[j]*3+nho)%du;
nho = (f[i-1].a[j]*3+nho)/du;
}
if(nho>0) f[i].a[++f[i].scs] = nho;
}
scanf("%d",&T);
for(int i=1;i<=T;i++)
{
scanf("%llu",&n);
//printf("%ull\n",n);
t=0;
so x;
x.scs = 1; x.a[1] = 0;
while(n!=0)
{
if(n%2==1)
sum(x,f[t]);
n=n/2;
t++;
}
print(x);
printf("\n");
}
//getch();
}