// 162_646.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define XX      (2)
//#define YY      (57885161)
#define YY      (57885)

//---------------------------------------------------------------------------
//      データ
//---------------------------------------------------------------------------
#define KETA    (10000)
typedef struct _T_DATA {
    int *data;                  // 10進数下KETA桁の配列。123456はdata[1]=12;data[0]=3456と格納される
    int d_n;                    // 有効配列数。上記例の場合、d_n=2;
    int d_a;                    // メモリ確保数(int配列個数)
} T_DATA;

//---------------------------------------------------------------------------
//      関数
//---------------------------------------------------------------------------
void T_DATA__Dec(T_DATA * dt);
void T_DATA__Delete(T_DATA * dt);
void T_DATA__Init(T_DATA * dt);
void T_DATA__Mult(T_DATA * dst, T_DATA * src, T_DATA * kt);
void T_DATA__Show(T_DATA * dt);
void T_DATA__SetInt(T_DATA * dt, int n);

//---------------------------------------------------------------------------
//      main
//---------------------------------------------------------------------------
int main()
{
    T_DATA ans, tmp;
    T_DATA kt;                  // 計算temp
    int y;

    T_DATA__Init(&ans);
    T_DATA__Init(&tmp);
    T_DATA__Init(&kt);

    T_DATA__SetInt(&ans, 1);
    T_DATA__SetInt(&tmp, XX);
    T_DATA__SetInt(&kt, 0);

    for (y = YY; y; y >>= 1) {
        fprintf(stderr, "現在の乗数. 0x%X\n", (unsigned int) y);
        if (y & 1) {
            T_DATA__Mult(&ans, &tmp, &kt);
        }
        T_DATA__Mult(&tmp, &tmp, &kt);
    }
    T_DATA__Dec(&ans);
    T_DATA__Show(&ans);

    T_DATA__Delete(&kt);
    T_DATA__Delete(&ans);
    T_DATA__Delete(&tmp);

    return 0;
}

//---------------------------------------------------------------------------
//      操作
//---------------------------------------------------------------------------

// 初期化
void T_DATA__Init(T_DATA * dt)
{
    // 最初に必要分確保してしまう
    dt->d_a = ((double) YY * log10((double) XX) + 1.0) / 2.0 + 1;
    dt->data = (int *) malloc(sizeof(int) * dt->d_a);
    if (dt->data == NULL) {
        fprintf(stderr, "メモリ確保エラー\n");
        exit(1);
    }
    dt->d_n = 0;
}

// 削除
void T_DATA__Delete(T_DATA * dt)
{
    if (dt->data) {
        free(dt->data);
        dt->data = NULL;
    }
    dt->d_n = dt->d_a = 0;
}

// 値をセット (n >= 0 であること)
void T_DATA__SetInt(T_DATA * dt, int n)
{
    memset(dt->data, 0x00, sizeof(int) * dt->d_a);
    dt->d_n = 0;
    while (1) {
        dt->data[dt->d_n++] = n % KETA;
        n /= KETA;
        if (n == 0) {
            break;
        }
    }
}

// -1する (dt->data > "1" であること)
void T_DATA__Dec(T_DATA * dt)
{
    int i;
    dt->data[0]--;
    for (i = 1; i < dt->d_n; i++) {
        if (dt->data[i - 1] < 0) {
            dt->data[i - 1] += KETA;
            dt->data[i]--;
            if (dt->data[i] == 0) {
                dt->d_n--;
            }
        } else {
            break;
        }
    }
}

// 掛け算
//  dst = dst * src
//  kt : 結果temp
void T_DATA__Mult(T_DATA * dst, T_DATA * src, T_DATA * kt)
{
    int i, j;
    T_DATA sw;

    T_DATA__SetInt(kt, 0);
    for (j = 0; j < src->d_n; j++) {
        for (i = 0; i < dst->d_n; i++) {
            kt->data[j + i] += src->data[j] * dst->data[i];
        }
        // 整形
        for (i = 0; i < kt->d_a - 1; i++) {
            if (kt->data[i] >= KETA) {
                kt->data[i + 1] += kt->data[i] / KETA;
                kt->data[i] %= KETA;
            }
        }
    }
    for (i = kt->d_a - 1; i > 0; --i) {
        if (kt->data[i]) {
            break;
        }
    }
    kt->d_n = i + 1;

    sw = *kt;
    *kt = *dst;
    *dst = sw;
}

// 標準出力
void T_DATA__Show(T_DATA * dt)
{
    int i;
    for (i = dt->d_n - 1; i >= 0; --i) {
        if (i == dt->d_n - 1) {
            printf("%d", dt->data[i]);
        } else {
            printf("%04d", dt->data[i]);
        }
    }
    printf("\n");
}

// End of 162_646.c