#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdint.h>
/// <summary>
/// 通過(guò)字符串初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]字符串首地址</param>
static void loadStr(int* a, const char* value) {
	int len = strlen(value);
	int left = len % 9;
	char s[8], * p = (char*)value + left;
	a[0] = ceil(len / 9.0);
	len = len / 9.0;
	for (int i = 1; i <= len; i++)
		sscanf(p + (len - i ) * 9, "%09d", &a[i]);
	if (left){
		sprintf(s, "%%0%dd", left);
		sscanf(value, s, &a[a[0]]);
	}
}
/// <summary>
/// 輸出到字符串，
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="str">[out]字符串，由外部停供緩沖區(qū)，需要保證長(zhǎng)度足夠</param>
static void toStr(int* a, char* str) {
	if (!a[0]) {
		sprintf(str, "0");
		return;
	}
	sprintf(str, "%d", a[a[0]]);
	str += strlen(str);
	for (int i = a[0]-1; i > 0; i--)
		sprintf(str +( a[0] -i-1)*9, "%09d", a[i]);
	str[(a[0]-1)*9] = '\0';
}
/// <summary>
/// 通過(guò)無(wú)符號(hào)整型初始化
/// </summary>
/// <param name="a">[in]高精度數(shù)組</param>
/// <param name="value">[in]整型值</param>
static void loadInt(int* a, uint64_t value) {
	a[0] = 0;
	while (value)a[++a[0]] = value % 1000000000, value /= 1000000000;
}

/// <summary>
/// 比較兩個(gè)高精度數(shù)的大小
/// </summary>
/// <param name="a">[in]第一個(gè)數(shù)</param>
/// <param name="b">[in]第二個(gè)數(shù)</param>
/// <returns>1是a>b,0是a==b,-1是a<b</returns>
static int compare(int* a, int* b) {
	if (a[0] > b[0])return 1;
	if (a[0] < b[0])return -1;
	for (int i = a[0]; i > 0; i--)
		if (a[i] > b[i])return 1;
		else if (a[i] < b[i])return -1;
	return 0;
}
/// <summary>
/// 復(fù)制
/// </summary>
/// <param name="a">[in]源</param>
/// <param name="b">[in]目標(biāo)</param>
static void copy(int* a, int* b) {
	memcpy(b, a, (a[0] + 1) * sizeof(int));
}
/// <summary>
/// 打印輸出結(jié)果
/// </summary>
static void print(int* a) {
	int i = a[0];
	printf("%d", a[i--]);
	for (; i > 0; i--)printf("%09d", a[i]);
}

/// <summary>
/// 加
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="b">[in]加數(shù)</param>
/// <param name="c">[out]結(jié)果</param>
static	void plus(int* a, int* b, int* c) {
	int* p;
	if (a[0] < b[0])p = a, a = b, b = p;//確保a長(zhǎng)度最大	
	int i = 1, alen = a[0], blen = b[0];
	c[0] = c[alen + 1] = 0;
	if (a != c)memcpy(c + blen + 1, a + blen + 1, (alen - blen) * sizeof(int));//a多出的部分直接拷貝到結(jié)果
	for (; i <= blen; i++) {
		c[i] = a[i] + b[i];
		if (c[i - 1] >= 1000000000)c[i - 1] -= 1000000000, c[i]++;//判斷上一位是否進(jìn)位	
	}
	i--;
	while (c[i++] >= 1000000000)c[i - 1] -= 1000000000, c[i]++;//繼續(xù)判斷進(jìn)位
	c[0] = c[alen + 1] ? alen + 1 : alen;//記錄長(zhǎng)度
}
/// <summary>
/// 加等于
///結(jié)果會(huì)保存在a中
/// </summary>
/// <param name="a">[in]被加數(shù)</param>
/// <param name="b">[in]加數(shù)</param>
static	void plusq(int* a, int* b) {
	plus(a, b, a);
}

/// <summary>
/// 減
/// </summary>
/// <param name="a">[in]被減數(shù),被減數(shù)必須大于等于減數(shù)</param>
/// <param name="b">[in]減數(shù)</param>
/// <param name="c">[out]結(jié)果</param>
static	void sub(int* a, int* b, int* c) {
	int i = 1, alen = a[0];
	if (a != c)memcpy(c + b[0] + 1, a + b[0] + 1, (a[0] - b[0]) * sizeof(int));//a多出的部分直接拷貝到結(jié)果
	c[0] = 1;
	for (; i <= b[0]; i++) {
		c[i] = a[i] - b[i];
		if (c[i - 1] < 0)c[i - 1] += 1000000000, c[i] --;//判斷上一位是否補(bǔ)位		
	}
	i--;
	while (c[i++] < 0)c[i - 1] += 1000000000, c[i]--;//繼續(xù)判斷補(bǔ)位	
	while (!c[alen--]); c[0] = alen + 1;//記錄長(zhǎng)度
}
/// <summary>
/// 減法等于
///結(jié)果會(huì)保存在a中
/// </summary>
/// <param name="a">[in]被減數(shù)，被減數(shù)必須大于等于減數(shù)</param>
/// <param name="b">[in]減數(shù)</param>
static	void subq(int* a, int* b) {
	sub(a, b, a);
}

/// <summary>
/// 乘
/// </summary>
/// <param name="a">[in]被乘數(shù)</param>
/// <param name="b">[in]乘數(shù)</param>
/// <param name="c">[out]結(jié)果，數(shù)組長(zhǎng)度必須大于等于aLen+bLen+1</param>
static	void mul(int* a, int* b, int c[]) {
	int len = a[0] + b[0], d = 0;
	memset(c, 0, sizeof(int) * (len + 1));
	b[b[0] + 1] = 0; c[0] = 1;//防止越界
	for (int i = 1; i <= a[0]; i++)
		for (int j = 1; j <= b[0] + 1; j++){
			int64_t t = (int64_t)a[i] * b[j] + c[j + i - 1] + d;
			c[j + i - 1] = t % 1000000000;
			d = t / 1000000000;
		}
	while (!c[len])len--; c[0] = len;
}
/// <summary>
/// 乘等于
/// 累乘,結(jié)果存放于a
/// </summary>
/// <param name="a">[in]被乘數(shù)，數(shù)組長(zhǎng)度必須大于等于2aLen+bLen+1</param>
/// <param name="b">[in]乘數(shù)</param>
static	void mulq(int* a, int* b) {
	int* c = a + a[0] + b[0] + 1;
	memcpy(c, a, (a[0] + 1) * sizeof(int));
	mul(c, b, a);
}

/// <summary>
/// 除法
/// 依賴減法subq
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="c">[out]商，數(shù)組長(zhǎng)度大于等于3aLen-bLen+1</param>
/// <param name="mod">[out]余數(shù)，可以為NULL，數(shù)組長(zhǎng)度大于等于aLen</param>>
static void div(int* a, int* b, int* c, int* mod) {
	int len = a[0] - b[0] + 1, times, hTimes[32], * temp = c + a[0] + 1;
	if (!mod)mod = temp + 2*(a[0] + 1)+1;//緩沖區(qū)
	memcpy(mod, a, (a[0] + 1) * sizeof(int));
	memset(c, 0, sizeof(int) * (len + 1));
	memset(temp, 0, sizeof(int) * len);
	c[0] = 1;//防止while越界
	for (int i = len; i > 0; i--) {
		memcpy(temp + i, b + 1, sizeof(int) * b[0]);//升階	
		temp[0] = b[0] + i - 1;
		while (compare(mod, temp) != -1) {
			if (times = (mod[mod[0]] * ((mod[0] - temp[0]) ? 1000000000ll : 1)) / (temp[temp[0]] + (temp[0] == 1 ? 0 : 1)))//升倍數(shù)
			{
				loadInt(hTimes,times);
				mulq(temp, hTimes);
			}
			else times = 1;
			while (compare(mod, temp) != -1)subq(mod, temp), c[i] += times;	//減法
			memcpy(temp + i, b + 1, sizeof(int) * b[0]);//還原	
			temp[0] = b[0] + i - 1;
		}
	}
	while (!c[len])len--; c[0] = len;
}
/// <summary>
/// 除等于
/// 商保存在a
/// 依賴div
/// </summary>
/// <param name="a">[in]被除數(shù),被除數(shù)必須大于除數(shù)</param>
/// <param name="b">[in]除數(shù)</param>
/// <param name="mod">[out]余數(shù)，可以為NULL，數(shù)組長(zhǎng)度大于等于aLen</param>>
static void divq(int* a, int* b, int* mod) {
	div(a, b, a, mod);
}

#include<Windows.h>
#include <iostream>
static int a[819200];
static int b[819200];
static int c[819200];
static int mod[819200];
static char str[81920];
/// <summary>
/// 返回當(dāng)前時(shí)間
/// </summary>
/// <returns>當(dāng)前時(shí)間，單位秒，精度微秒</returns>
static double  getCurrentTime()
{
	LARGE_INTEGER ticks, Frequency;
	QueryPerformanceFrequency(&Frequency);
	QueryPerformanceCounter(&ticks);
	return  (double)ticks.QuadPart / (double)Frequency.QuadPart;
}
/// <summary>
/// 性能測(cè)試
/// </summary>
static void test() {
	double d = getCurrentTime();
	loadStr(a, "50000");
	loadInt(b, 50000);
	for (int64_t i = 1; i <= 500000; i++) {
		plus(a, b, c);
	}
	printf("plus  performence   1: %llfs\n", getCurrentTime() - d);
	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadInt(b, 5);
	for (int64_t i = 1; i <= 500000; i++) {
		plus(a, b, c);
	}
	printf("plus  performence   2: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500000; i++) {
		plus(b, a, c);
	}
	printf("plus  performence   3: %llfs\n", getCurrentTime() - d);


	d = getCurrentTime();
	loadStr(a, "50000");
	loadInt(b, 50000);
	for (int64_t i = 1; i <= 500000; i++) {
		plusq(a, b);
	}
	printf("plusq performence   1: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	for (int64_t i = 500000000; i <= 500000000 + 500000; i++) {
		loadInt(b, i);
		plusq(a, b);
	}
	printf("plusq performence   2: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(b, "999999999999999999999999999999999999999999999999999999999999999999");
	for (int64_t i = 500000000; i <= 500000000 + 500000; i++) {
		loadInt(a, i);
		plusq(a, b);

	}
	printf("plusq performence   3: %llfs\n", getCurrentTime() - d);


	d = getCurrentTime();
	loadStr(a, "50000");
	loadInt(b, 10000);
	for (int64_t i = 1; i <= 500000; i++) {
		sub(a, b, c);
	}
	printf("sub   performence   1: %llfs\n", getCurrentTime() - d);



	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadInt(b, 11111);
	for (int64_t i = 1; i <= 500000; i++) {
		sub(a, b, c);
	}
	printf("sub   performence   2: %llfs\n", getCurrentTime() - d);


	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500000; i++) {
		sub(a, b, c);
	}
	printf("sub   performence   3: %llfs\n", getCurrentTime() - d);



	d = getCurrentTime();
	loadStr(a, "50000000000");
	loadInt(b, 500000);
	for (int64_t i = 1; i <= 500000; i++) {
		subq(a, b);
	}
	printf("subq  performence   1: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadInt(b, 11111);
	for (int64_t i = 1; i <= 500000; i++) {
		subq(a, b);
	}
	printf("subq  performence   2: %llfs\n", getCurrentTime() - d);


	
	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500000; i++) {
		subq(a, b);
	}
	printf("subq  performence   3: %llfs\n", getCurrentTime() - d);


	d = getCurrentTime();
	loadStr(a, "50000");
	loadInt(b, 12345);
	for (int64_t i = 1; i <= 500000; i++) {
		mul(a, b, c);
	}
	printf("mul   performence   1: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadInt(b, 12345);
	for (int64_t i = 1; i <= 500000; i++) {
		mul(a, b, c);
	}
	printf("mul   performence   2: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500000; i++) {
		mul(b, a, c);
	}
	printf("mul   performence   3: %llfs\n", getCurrentTime() - d);


	d = getCurrentTime();
	loadStr(a, "2");
	loadInt(b, 2);
	for (int64_t i = 1; i <= 1000; i++) {
		mulq(a, b);
	}
	printf("mulq  performence   1: %llfs\n", getCurrentTime() - d);
	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadInt(b, 2);
	for (int64_t i = 1; i <= 1000; i++) {
		mulq(a, b);
	}
	printf("mulq  performence   2: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 1000; i++) {
		mulq(b, a);
	}
	printf("mulq  performence   3: %llfs\n", getCurrentTime() - d);



	d = getCurrentTime();
	loadStr(a, "50000");
	loadInt(b, 12345);
	for (int64_t i = 1; i <= 500000; i++) {
		div(a, b, c, mod);
	}
	printf("div   performence   1: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadInt(b, 12345);
	for (int64_t i = 1; i <= 500000; i++) {
		div(a, b, c, NULL);
	}
	printf("div   performence   2: %llfs\n", getCurrentTime() - d);

	d = getCurrentTime();
	loadStr(a, "100000000000000000000000000000000000000000000000000000000000000000");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500000; i++) {
		div(a, b, c, mod);
	}
	printf("div   performence   3: %llfs\n", getCurrentTime() - d);



	loadStr(a, "1");
	loadStr(b, "2");
	for (int64_t i = 1; i <= 1000; i++) {
		mulq(a, b);
	}
	d = getCurrentTime();
	for (int64_t i = 1; i <= 1000; i++) {
		divq(a, b, mod);
	}
	printf("divq  performence   1: %llfs\n", getCurrentTime() - d);

	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadStr(b, "2");
	for (int64_t i = 1; i <= 1000; i++) {
		mulq(a, b);
	}
	d = getCurrentTime();
	for (int64_t i = 1; i <= 1000; i++) {
		divq(a, b, mod);
	}
	printf("divq  performence   2: %llfs\n", getCurrentTime() - d);



	loadStr(a, "999999999999999999999999999999999999999999999999999999999999999999");
	loadStr(b, "11111111111111111111111111111111111111");
	for (int64_t i = 1; i <= 500; i++) {
		mulq(a, b);
	}
	d = getCurrentTime();
	for (int64_t i = 1; i <= 500; i++) {
		divq(a, b, mod);
	}
	printf("divq  performence   3: %llfs\n", getCurrentTime() - d);
}