#include "stdafx.h"
#include "iostream"
typedef __int64 INT64;
void HeroNeedThree(INT64* subset, unsigned int n)
{
// base3[k]=3^k
static INT64 base3[32]=
{
0x1,0x3,0x9,0x1b,0x51,0xf3,0x2d9,0x88b,
0x19a1,0x4ce3,0xe6a9,0x2b3fb,0x81bf1,0x1853d3,0x48fb79,0xdaf26b,
0x290d741,0x7b285c3,0x17179149,0x4546b3db,0xcfd41b91,0x26f7c52b3,0x74e74f819,0x15eb5ee84b,
0x41c21cb8e1,0xc546562aa3,0x24fd3027fe9,0x6ef79077fbb,0x14ce6b167f31,0x3e6b41437d93,0xbb41c3ca78b9,0x231c54b5f6a2b
};
// base2[k]=2^k
static unsigned int base2[32]=
{
0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,
0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,
0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000
};
INT64 num=0;
n--;
for(int i=31;i>=0;--i)
{
if(n & base2[i]) // 计算n的第i位上是否是1
{
subset[++num]=base3[i];
}
}
subset[0]=num;
}

int main(int argc, char* argv[])
{

unsigned int n;
INT64 subset[40];
std::cin>>n;
HeroNeedThree(subset,n);
printf("%I64d\n",subset[0]);
for(INT64 i=0;i<subset[0];++i)
printf("%I64d,",subset[i+1]);
return 0;
}

void HeroNeedThree(INT64* subset, unsigned int n)
{
static INT64 s_HelperCount[] =
{
1, 3, 9, 27,
81, 243, 729, 2187,
6561, 19683, 59049, 177147,
531441, 1594323, 4782969, 14348907,
43046721, 129140163, 387420489, 1162261467,
3486784401, 10460353203, 31381059609, 94143178827,
282429536481, 847288609443, 2541865828329, 7625597484987,
22876792454961, 68630377364883, 205891132094649,617673396283947,
};

int idx = 32;
int cnt = 0;

n--;
while(idx>0)
{
idx--;
if(((n)&(1<<(idx))))
{
cnt++;
subset[cnt] = s_HelperCount[idx];
}


}
subset[0] = cnt;
}

void HeroNeedThree(INT64* subset, unsigned int n)
{
static INT64 powof3[32];
static int initialized=0;
int i;
if(!initialized)
{
//你也可以在定义时直接初始化这个数组,如果你有耐心写一堆数字的话^_^
for(i=1,powof3[0]=1;i<32;i++)
{
powof3[i]=powof3[i-1]*3;
}
initialized=1;
}

for(i=31,subset[0]=0,n--;i>=0;i--)
{
if(n&(1<<i)) //检查对应2进制位是否为1
{
subset[++subset[0]]=powof3[i];
}
}
}