#include <stdio.h>
#include <string.h>
#define MBI_DATA_NUM 10001
typedef struct tag_mbi_t
{
unsigned short data[MBI_DATA_NUM];
int top;
}mbi_t;
void mbi_zero(mbi_t *mbi)
{
memset(mbi, 0, sizeof(mbi_t));
}
void mbi_copy(mbi_t *a, const mbi_t *b)
{
memcpy(a, b, sizeof(mbi_t));
}
// !注意! アドレス r==a または r==b が成り立つときはうまく計算できません
void mbi_mul(mbi_t *r, const mbi_t *a, const mbi_t *b)
{
int i, j, j_max=0;
long temp, carry;
mbi_zero(r);
for(i=0;i<=b->top;i++)
{
j_max=MBI_DATA_NUM-1-i;
if(j_max>a->top) j_max=a->top;
carry=0;
for(j=0;j<=j_max;j++)
{
temp=carry+a->data[j]*b->data[i]+r->data[i+j];
r->data[i+j]=temp%10000;
carry=temp/10000;
}
for(;carry && i+j<MBI_DATA_NUM;j++)
{
temp=carry+r->data[i+j];
r->data[i+j]=temp%10000;
carry=temp/10000;
}
r->top=i+j-1;
}
for(i=r->top;i>0;i--)
{
if(r->data[i]) break;
}
r->top=i;
}
void mbi_print(const mbi_t *mbi)
{
int i;
i=mbi->top;
printf("%d", mbi->data[i]);
for(i--;i>=0;i--)
{
printf("%04d", mbi->data[i]);
}
printf("\n");
}
int main(void)
{
static mbi_t result, base, temp;
int m=10000, n=10000;
base.data[0]=m;
result.data[0]=1;
for(;n>0;n>>=1)
{
if(n & 1)
{
mbi_copy(&temp, &result);
mbi_mul(&result, &temp, &base);
}
mbi_copy(&temp, &base);
mbi_mul(&base, &temp, &temp);
}
mbi_print(&result);
return 0;
}