#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <math.h>
#include <queue>
#include <memory.h>
using namespace std;
#define bigNum_size 220 //大数的段数，bigNum能表示的最大长度 = bigNum_size*log(mod)
#define mod 100000 //每段存储数字的长度为0的个数
char A[1010], B[1010];
struct bigNum
{
int a[bigNum_size];
int len;//存储大数的段数，初始化时长度都为1，表示的值默认为0
bigNum()
{
len = 1;
memset(a, 0, sizeof(a));
}
bigNum(char *str)
{
int n = strlen(str);
int t = 0;
int m, i, k = 0, inf = 1;
memset(a, 0, sizeof(a));
for (i = n - 1; i >= 0; i--)
{
m = str[i] - '0';
k += inf*m;
inf *= 10;
if (inf == mod)
{
inf = 1;
a[t++] = k;
k = 0;
}
}
a[t++] = k;
while (t > 1 && a[t-1] == 0) t--;
len = t;
}
bigNum(int x)
{
memset(a, 0, sizeof(a));
a[0] = x;
int i = 1;
while (a[i-1] >= mod)
{
a[i] = a[i-1]/mod;
a[i-1] %= mod;
i++;
}
len = i;
}
};
bigNum operator +(bigNum x, bigNum y)
//重载运算符"+"，执行两个大数的加法并返回结果
{
int i, n;
bigNum s;
if (x.len < y.len)
{
bigNum temp = x;
x = y;
y = temp;
}
n = y.len;
for (i = 0; i < n; i++)
{
x.a[i] += y.a[i];
x.a[i+1] += x.a[i]/mod;
x.a[i] %= mod;
}
while (x.a[n] > mod)
{
x.a[n+1] += x.a[n]/mod;
n++;
}
if (x.a[x.len])x.len++;
return x;
}
bigNum operator *(int m, bigNum x)
//重载运算符"*"，执行一个大数乘以一个int内的数字，并返回结果
{
int i, k = 0;
for (i = 0; i < x.len; i++)
{
x.a[i] = x.a[i] * m + k;
k = x.a[i] / mod;
x.a[i] %= mod;
}
while (k)
{
x.a[i] = k%mod;
k /= mod;
i++;
}
x.len = i;
return x;
}
bool operator < (bigNum x, bigNum y)
//比较两个大数的大小，如果x<y返回true,否则返回false
{
if (x.len < y.len)
return true;
if (x.len > y.len)
return false;
int i;
for (i = x.len - 1; i >= 0; i--)
if (x.a[i] < y.a[i])
return true;
else if (x.a[i] > y.a[i])
return false;
return false;
}
bigNum operator - (bigNum x, bigNum y)
//计算两个大数的减法，其中保证x>y。
{
bigNum s;
int i;
int k = 0;
for (i = 0; i < y.len; i++)
{
if (x.a[i] == -1)
{
x.a[i] = mod - 1;
x.a[i+1]--;
}
if (x.a[i] >= y.a[i])
s.a[i] = x.a[i] - y.a[i];
else
{
s.a[i] = mod + x.a[i] - y.a[i];
x.a[i+1]--;
}
}
while (i < x.len)
{
if (x.a[i] == -1)
{
x.a[i] = mod - 1;
x.a[i+1]--;
}
s.a[i] = x.a[i];
i++;
}
s.len = i;
while (s.a[s.len - 1] == 0)
{
s.len--;
}
if (s.len == 0)
s.len = 1;
return s;
}
bigNum sqrt_bignum(bigNum x)
//开根号，只能对大的正整数开方求得整数不分，
//如果要对小数开方或对正整数开方求小数点后面的数字，
//可以将这个数扩大10^(2*k)倍在进行开方。
// 在调用开发函数时， mod = 10 才能完成。所以效率不是很高。
{
bigNum s, md;
bigNum p;
bigNum temp;
int n = x.len;
int k;
int i;
if (n%2)
{
if (x.a[n-1] > 8)
{
s.a[0] = 3;
md.a[0] = x.a[n-1] - 9;
}
else if (x.a[n-1] > 3)
{
s.a[0] = 2;
md.a[0] = x.a[n-1] - 4;
}
else
{
s.a[0] = 1;
md.a[0] = x.a[n-1] - 1;
}
n--;
}
for (i = n - 1; i > 0; i = i - 2)
{
p.a[1] = x.a[i];
p.a[0] = x.a[i-1];
p.len = 2;
md = (100 * md + p);
for (k = 1; k < 10; k++)
{
p.a[0] = k;
p.len = 1;
temp = 20*s + p;
temp = k*temp;
if (md < temp)
break;
}
k--;
p.a[0] = k;
p.len = 1;
temp = 20*s + p;
temp = k*temp;
md = md - temp;
s = 10*s + p;
}
return s;
}
void output(bigNum x)
//输出大数的函数
{
int i;
int n = x.len;
printf("%d", x.a[n-1]);
for (i = n - 2; i >= 0; i--)
printf("%05d", x.a[i]);// %d05d与mod大小有关,即每段的数字个数。
printf("\n");
}
int main()
{
return 0;
}