PhoenixWright

#include <iostream>
using namespace std;
#include <math.h>
#define SWAP(a, b) a ^= b ^= a ^= b
const int  M = 10000;							//几进制
const int W = 4;		//对应M进制时每个数组存放几位 (int)(log10(M-1.0))+1;
#if M > 10000
#define Elem long long
#else
#define Elem int
#endif
const int N = 1000;			//要计算的数最大有几位
struct BigNum {
	Elem a[N/W+1];
	int l, len;
	BigNum() {
		l = len = 1;
		memset(a, 0, sizeof(a));
	}
	BigNum(char *p) {
		memset(a, 0, sizeof(a));
		split(p);
	}
	void split(char *p) {
		int i, j, k, s;
		len = strlen(p);
		l = len / W;
		if((s = len % W)) l++;
		else s = W;
		a[0] = 0;
		for(i = 0; i < s; i++) a[0] = a[0] * 10 + p[i] - '0';
		for(i = s, j = 1; j < l; j++) {
			a[j] = 0;
			for(k = 0; k < W; k++, i++)
				a[j] = a[j] * 10 + p[i] - '0';
		}
	}
	void print() {
		int i;
		printf("%d", a[0]);
		for(i = 1; i < l; i++) printf("%04d", a[i]);
		putchar('\n');
	}
	BigNum operator +(BigNum b) {
		BigNum c;
		int i, j, k, f = 0;
		for(i = l-1, j = b.l-1, k = 0; i >= 0 || j >= 0; i--, j--, k++) {
			c.a[k] = f;
			if(i >= 0) c.a[k] += a[i];
			if(j >= 0) c.a[k] += b.a[j];
			if(c.a[k] >= M) f = c.a[k] / M, c.a[k] %= M;
			else f = 0;
		}
		if(f == 1) c.a[k++] = 1;
		c.l = k;
		if(c.l == 1 && c.a[0] < 10) c.len = 1;
		else c.len = (c.l -  1)* W + (int)(log10((double)c.a[0]))+1;
		for(i = 0, j = k - 1; i < j; i++, j--)
			SWAP(c.a[i], c.a[j]);
		return c;
	}
	BigNum operator -(BigNum b) {
		BigNum c;
		int la = l-1, lb = b.l-1, i, j, m = 0, k;
		for(i = la, j = lb, k = 0; i >= 0 && j >= 0; i--, j--, k++) {
			c.a[k] = a[i] + M - b.a[j] - m;
			if(c.a[k] >= M) c.a[k] -= M, m = 0;
			else m = 1;
		}
		while(i >= 0) {
			c.a[k] = a[i] + M - m;
			if(c.a[k] >= M) c.a[k] -= M, m = 0;
			else m = 1;
			k++, i--;
		}
		k--;
		while(c.a[k] == 0 && k > 0) k--;
		c.l = k + 1;
		for(i = 0, j = c.l-1; i < j; i++, j--) SWAP(c.a[i], c.a[j]);
		if(c.l == 1 && c.a[0] < 10) c.len = 1;
		else c.len = (c.l -  1)* W + (int)(log10((double)c.a[0]))+1;
		return c;
	}
	BigNum operator *(int data) {
		BigNum t;
		int f[N/W+1] = {0};
		int i, j = 2, fl = 0, n;
		for(i = 0; i < l; i++, j++) {
			f[j] = a[i] * data;
		}
		n = j;
		for(j--; j >= 0; j--) {
			f[j] += fl;
			fl = f[j] / M;
			f[j] %= M;
		}
		i = 0;
		while(f[i] == 0 && i < n) i++;
		if(i == n) i--;
		for(j = 0; i < n; j++, i++) t.a[j] = f[i];
		t.l = j;
		if(t.l == 1 && t.a[0] < 10) t.len = 1;
		else t.len = (t.l -  1)* W + (int)(log10((double)t.a[0]))+1;
		return t;
	}
	BigNum operator *(BigNum b) {
		BigNum c;
		int i, j;
		Elem *s, r;
		int la = l, lb = b.l, p;
		s = (Elem*)malloc(sizeof(Elem) * (l+b.l));
		memset(s, 0, sizeof(Elem) * (la+lb));
		for(i = lb - 1; i >= 0; i--) {
			for(j = la - 1, r = 0; p = la + lb - i - j - 2, j >= 0; j--) {
				r += (Elem)a[j] * b.a[i];
				s[p] += r % M;
				r /= M;
				if(s[p] >= M) s[p] -= M, r++;
			}
			if(r) s[p] = r;
		}
		for(i = la + lb - 1, j = 0; !s[i] && i > 0; i--);
		while(i >= 0) c.a[j++] = s[i--];
		c.l = j;
		if(c.l == 1 && c.a[0] < 10) c.len = 1;
		else c.len = (c.l -  1)* W + (int)(log10((double)c.a[0]))+1;
		free(s);
		return c;
	}	
	BigNum operator /(int b) {
		int i, t = 0, j, f = 0;
		BigNum c;
		for(i = 0, j = 0; i < l; i++) {
			t = t * M + a[i];
			if(!f && t / b) {c.a[j++] = t / b; f = 1;}
			else if(f) c.a[j++] = t / b;
			t %= b;
		}
		c.l = j;
		if(c.l == 1 && c.a[0] < 10) c.len = 1;
		else c.len = (c.l -  1)* W + (int)(log10((double)c.a[0]))+1;
		return c;
	}
};