//High Calc
#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

#define base      10000
//長度
//代表在數組中每個單元中的權值
#define base_len  4
//每個單元中數據的
#define array_len 20000
//數組的長度
//int a[], a[0] is length, a[1] is low
template <class T>inline
T max(T i,T j){return i>j?i:j;}
template <class T>inline
T min(T i,T j){return i<j?i:j;}

void _plus (int *a,int *b,int *c);//加法
void _minus(int *a,int *b,int *c);//減法
//必須保證 a>b
void _mul  (int *a,int *b,int *c);//乘法
void _mul  (int *a,int  b,int *c);//乘法
void _fac  (int  n,int *a);
//n!
void _disp (int *a,ostream &os);
int _cmp(int *a,int *b);
void _change(char*p,char*q,int *a,int *b);
/*
比較a,b中存儲的大數據的大小 a>b返回1  
a<b返回0；
a=b返回-1；
*/
void main(){
	int a[array_len]={10,1234,4356,8986,4263,6648,3201,8045,4125,7654,4321};
	int b[array_len]={9,2343,4321,5463,4315,7641,543,4435,3423,5};
	int c[array_len];
	_disp(a,cout);
	cout<<'+';
	_disp(b,cout);
	cout<<'=';
	_plus(a,b,c);
	_disp(c,cout);
	cout<<endl<<endl;

	_disp(a,cout);
	cout<<'-';
	_disp(b,cout);
	cout<<'=';
	_minus(a,b,c);
	_disp(c,cout);
	cout<<endl<<endl;

	_disp(a,cout);
	cout<<"*178=";
	_mul(a,178,c);
	_disp(c,cout); 
	cout<<endl<<endl;

	_disp(a,cout);
	cout<<'*';
	_disp(b,cout);
	cout<<'=';
	_mul(a,b,c);
	_disp(c,cout);
	cout<<endl<<endl;

	cout<<"123!=";
	_fac(123,c);
	_disp(c,cout);
	cout<<endl;

};
//加法結果保存c中
//g代表進位
void _plus(int *a,int *b,int *c){
	int i,k,t,g=0;
	int *p;
	k=min(*a,*b);
	for(i=1;i<=k;i++){
		t=*(a+i)+*(b+i)+g;
		*(c+i)=t%base;
		g=t/base;
	}
	for(p=*a>*b?a:b,*c=k=max(*a,*b);i<=k;i++){
		t=*(p+i)+g;
		*(c+i)=t%base;
		g=t/base;
	}
	if(g)*(c+ ++(*c))=g;
}
void _minus(int *a,int *b,int *c){
	//a must bigger than b
	int i,k,t,g=0;
	k=*b;
	for(i=1;i<=k;i++){
		t=*(a+i)-*(b+i)-g;
		g=t<0;
		if(g)t+=base;
		*(c+i)=t;
	}
	for(*c=k=*a;i<=k;i++){
		t=*(a+i)-g;
		g=t<0;
		if(g)t+=base;
		*(c+i)=t;
	}
	while(!*(c+*c)&&*c>1)(*c)--;
}
//減法
void _mul(int *a,int *b,int *c){
	int t[array_len];
	memset(c,0,array_len);
	int i,k=*b;
	for(i=1;i<=k;i++){
		_mul(a,*(b+i),t);
		memcpy(t+i,t+1,*t*sizeof(int));
		memset(t+1,0,sizeof(int)*(i-1));
		*t+=i-1;
		_plus(t,c,c);
	}
}
//乘法
void _mul(int *a,int b,int *c){
	int i,k,t,g=0;
	*c=k=*a;
	for(i=1;i<=k;i++){
		t=*(a+i)*b+g;
		*(c+i)=t%base;
		g=t/base;
	}
	if(g)*(c+ ++(*c))=g;
}
//a!n
void _fac(int n,int *a){
	*a=*(a+1)=1;
	for(int i=1;i<=n;i++)
		_mul(a,i,a);
}
//輸出從高位輸出
void _disp(int *a,ostream &os){
	int i,k=*a;
	os<<*(a+k)<<setfill('0');
	for(i=k-1;i>0;i--)
		os<<setw(base_len)<<*(a+i);
	os<<setfill(' ');
}
//比較兩個的大小
int cmp(int *a,int *b )
{
if(*a>*b)return 1;
if(*a<*b)return 0; 
for(int i=*a;i>0;i--)
	{if(*(a+i)>*(b+i))return 1;
     if(*(a+i)<*(b+i))return 0; 
	}
return -1;
}
//p存儲對應a中的字符形式 q存儲對應b中的字符形式
//該函數實現由字符串向整形數組存儲的轉換
//整形數組的存儲格式
//以a為例int a[], a[0] is length, a[1] is low
void _change(char*v,char*p,int *a,int *b)
{
int i,j=1,len1,len2;
len1=strlen(v);len2=strlen(p);
memset(a,0,100*sizeof(int));memset(b,0,100*sizeof(int));
//這里是對于整形結構存儲結構中數組置0
//根據情況來定是否要這個代碼
//內部函數說明atoi(const char*)實現從串向數組的轉換從傳入的串指針處開始一直轉換的遇到非數值字符
for(i=len1>base_len? len1-base_len:0;i>0;i=i-base_len)//
	{a[j++]=atoi(v+i);
     v[i]='*';
	}
a[j]=atoi(v);
a[0]=j;j=1;
for(i=len2>base_len?len2-base_len:0;i>0;i=i-base_len)//
	{b[j++]=atoi(p+i);
     p[i]='*';
	}
b[j]=atoi(p);
b[0]=j;
}