这里的高精度都是要去掉前导0的，
第一题：424 - Integer Inquiry
解题思路：模拟手动加法的运算过程，写一个高精度整数加法就可以了；减法，乘法，除法同样也是模拟手动过程。
解题代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
using namespace std; //#define LOCAL //Please annotate this line when you submit #ifdef WINDOWS
#define LL __int64
#define LLD "%I64d"
#else
#define LL long long
#define LLD "%lld"
#endif char num1[];
int num2[], ans[]; int add()
{
int len = strlen(num1);
if (len == && num1[] == '')
return ;
memset(num2, , sizeof(num2));
int k = ;
for (int i = len - ; i >= ; i --)
{
num2[k++] = num1[i] - '';
}
int up = ;
for (int i = ; i < ; i ++)
{
ans[i] = ans[i] + num2[i] + up;
up = ans[i]/;
ans[i] %= ;
}
return ;
} int main()
{ #ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
memset (ans, , sizeof(ans));
int cun = ;
while ()
{
scanf ("%s", num1);
if (add())
continue;
else
{
int i;
for (i = ; i >= ; i --)
if (ans[i])
break;
for ( ; i >= ; i --)
printf("%d", ans[i]);
puts("");
break;
}
}
return ;
}
第二题：10106 - Product
解题思路：此题是高精度整数乘法。
解题代码：
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
using namespace std; //#define LOCAL //Please annotate this line when you submit #ifdef WINDOWS
#define LL __int64
#define LLD "%I64d"
#else
#define LL long long
#define LLD "%lld"
#endif const int max_n = ;
int num1[max_n], num2[max_n], ans[*max_n];
char str1[max_n], str2[max_n]; void ride()
{
memset(num1, , sizeof(num1));
memset(num2, , sizeof(num2));
memset(ans, , sizeof(ans));
int len1 = strlen(str1);
int k = , i;
for (i = len1-; i >= ; i--)
num1[k++] = str1[i] - '';
int len2 = strlen(str2);
for (i = len2 - , k = ; i >= ; i--)
num2[k++] = str2[i] - '';
int up = ;
for (int j = ; j < max_n; j ++)
{
for (i = ; i < max_n; i ++)
{
ans[i+j] += num1[i]*num2[j] + up;
up = ans[i+j]/;
ans[i+j] %= ;
}
}
for (i = *max_n-; i >= ; i --)
if (ans[i])
break;
if (i < )
i = ;
for ( ; i >= ; i --)
printf("%d", ans[i]);
puts("");
} int main()
{ #ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
while (~scanf("%s", str1))
{
scanf("%s", str2);
ride();
}
return ;
}
第三题：465 - Overflow
解题思路：
此题也是高精度加法，乘法。当然晚上有用atof秒杀的，既然是专题，还是写个高精度吧！这题也需要去掉前导0，比较与int型大小时，条件要判断好，我在这个条件这里因为少写了一个if语句结果WA了n次。o(╯□╰)o
ps：int数据最大值是2147483647；
解题代码：
#ifdef WINDOWS
#define LL __int64
#define LLD "%I64d"
#else
#define LL long long
#define LLD "%lld"
#endif
//#define LOCAL //Please annotate this line when you submit
/********************************************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
using namespace std;
const int max_n = ;
int num1[max_n], num2[max_n], ans[max_n];
char str1[max_n], str2[max_n], ope;
bool jug1, jug2, juga;
const int MAX[] = {,,,,,,,,,};
int pos1, pos2; void add()
{
int up = ;
int i;
int t = pos1 > pos2 ? pos1 : pos2;
for (i = ; i <= t+; i ++)
{
ans[i] = num1[i] + num2[i] + up;
up = ans[i]/;
ans[i] %= ;
}
for (i = t+; i >= ; i --)
if (ans[i])
break;
/*
for (int j = i; j >= 0; j --)
cout << ans[j];
cout << endl;
*/
if (i > )
juga = true;
else if (i == )
for (i = ; i >= ; i --)
{
if (ans[i] > MAX[i])
{
juga = true;
break;
}
if (ans[i] < MAX[i])
break;
}
} void mul()
{
int up = ;
int i;
for (i = ; i <= pos1 + ; i ++)
for (int j = ; j <= pos2 + ; j ++)
{
ans[i+j] += num1[i]*num2[j] + up;
up = ans[i+j]/;
ans[i+j] %= ;
}
for (i = pos1+pos2+; i >= ; i --)
if (ans[i])
break;
/*
for (int j = i; j >= 0; j --)
cout << ans[j];
cout << endl;
*/
if (i > )
juga = true;
else if (i == )
for (; i >= ; i --)
{
if (ans[i] > MAX[i])
{
juga = true;
break;
}
if (ans[i] < MAX[i])
break;
}
} int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
while (~scanf ("%s %c %s", str1, &ope, str2))
{
jug1 = jug2 = juga = false;
memset(num1, , sizeof (num1));
memset(num2, , sizeof (num2));
memset (ans, , sizeof (ans));
pos1 = ;
for (int i = strlen(str1) - , k = ; i >= ; i --)
{
num1[k ++] = str1[i] - '';
if (num1[k-])
pos1 = k - ;
}
if (pos1 > )
{
juga = true;
jug1 = true;
}
else if(pos1 == )
{
for (int i = ; i >= ; i --)
{
if (num1[i] > MAX[i])
{
juga = true;
jug1 = true;
break;
}
if (num1[i] < MAX[i])
break;
}
}
pos2 = ;
for (int i = strlen(str2) - , k = ; i >= ; i --)
{
num2[k ++] = str2[i] - '';
if (num2[k-])
pos2 = k-;
}
if (pos2 > )
{
jug2 = true;
juga = true;
}
else if (pos2 == )
{
for (int i = ; i >= ; i--)
{
if (num2[i] > MAX[i])
{
juga = true;
jug2 = true;
break;
}
if (num2[i] < MAX[i])
break;
}
}
if ((pos1 == && num1[pos1] == ) || (pos2 == && num2[pos2] == ))
juga = false;
printf("%s %c %s\n", str1, ope, str2);
if (ope == '+')
add();
else if (ope == '*')
mul();
else if (ope != '+' && ope != '*')
juga = false;
if (jug1)
printf("first number too big\n");
if (jug2)
printf("second number too big\n");
if (juga)
printf("result too big\n");
} return ;
}
第四题：748 - Exponentiation
解题思路：高精度乘法；但这里是浮点型，我们只需把小数点去了，进行计算，输出时再找准小数点位置输出就可，至于小数点位置的话，举个列子：13.4*3.54，两个数长度都是4，第一个数字小数点在 2 的位置，小数点位数为 4-2-1 = 1；第二个数小数点在 1 的位置，小数点位数为 4 - 1 - 1 = 2；他们的乘积为 47.436，小数点的位数为 3 = 1 + 2；也就是数字一的位数与数字二的位数的和。此题还需将后缀0去掉。
解题代码：
#ifdef WINDOWS
#define LL __int64
#define LLD "%I64d"
#else
#define LL long long
#define LLD "%lld"
#endif
//#define LOCAL //Please annotate this line when you submit
/********************************************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
using namespace std;
const int max_n = ;
string str;
int num1[max_n], num2[max_n], ans[*max_n];
int point, Pow;
int len1, len2; void change()
{
memset(num1, , sizeof(num1));
memset(num2, , sizeof(num2));
point = str.find(".");
int len = str.length();
if (point != -)
point = len - point - ;
int k = ;
for (int i = len - ; i >= ; i --)
{
if (str[i] == '.')
continue;
num1[k] = str[i] - '';
num2[k ++] = str[i] - '';
}
len1 = len2 = k;
} void mult()
{
memset(ans, , sizeof (ans));
int up = ;
for (int i = ; i <= len1; i ++)
for (int j = ; j <= len2; j ++)
{
ans[i+j] += num1[i]*num2[j] + up;
up = ans[i+j]/;
ans[i+j] %= ;
}
int bg;
for (int i = len1 + len2; i >= ; i--)
if (ans[i])
{
bg = i;
break;
} for (int i = ; i <= bg; i ++)
num2[i] = ans[i];
len2 = bg + ;
} void output()
{
int i, j, k;
for (i = max_n-; i >=; i--)
{
if(num2[i])
break;
if (i == Pow*point)
{
i --;
break;
}
}
for (j = ; j <= i; j ++)
{
if (num2[j])
break;
if (j == Pow*point)
{
j ++;
break;
}
}
if (i+ == Pow * point)
printf(".");
for (k = i; k >= j; k --)
{
printf("%d", num2[k]);
if (k == Pow*point && k > j)
printf(".");
}
printf("\n");
} int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
while (cin >> str)
{
scanf ("%d", &Pow);
change();
for (int i = ; i < Pow; i ++)
mult();
output();
}
return ;
}
第五题：10494 - If We Were a Child Again
解题思路：此题是高精度除法，题目只需高精度除以低精度，但我想练习一下就写了高精度除以高精度，过程是模拟短除法来做，配合高精度正整数减法。此题题意里除数没有包含0，但数据里我想应该是有的，因为我少了为0的判断就WA，加上就AC。所以0做为除数还是要判断一下。
解题代码：
//#define LOCAL //Please annotate this line when you submit
#ifdef WINDOWS
#define LL __int64
#define LLD "%I64d"
#else
#define LL long long
#define LLD "%lld"
#endif /********************************************************/
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <map>
#define CLE(name) memset(name, 0, sizeof(name))
using namespace std; const int max_n = ;
int num1[max_n], num2[max_n], num3[max_n];//被除数和除数
int len1, len2, len3;
string str1, ope, str2;
int len_str1, len_str2;
int get_num_pos;
int quo[max_n], res[max_n];//商和余数
int len_quo, len_res;
bool had_red; bool get_num3()
{
int i, k, j;
k = ;
len3 ++;
if (get_num_pos + len3 > len1)
{
for (i = len3 - ; i >= ; i --)
if (num3[i])
break;
for (j = i; j >= ; j --)
res[len_res++] = num3[j];
return false;
}
for (i = get_num_pos + len3 - ; i >= get_num_pos; i --)
num3[k ++] = num1[i];
return true;
} bool cpt()//将余数补在num1上
{
int i, j;
for (i = get_num_pos - , j = len_res - ; j >= ; j --, i --)
num1[i] = res[j];
get_num_pos = i + ;
if (get_num3())
{
for (i = ; i < len_res; i ++)
res[i] = ;
len_res = ;
return true;
}
else return false;
} void change()
{
CLE(num1); CLE(num2);
CLE(num3); CLE(res); CLE(quo); len_str1 = str1.length();
len_str2 = str2.length();
int k = ;
bool had = false;
for (int i = ; i < len_str1; i ++)
{
if (str1[i] == '' && !had)
continue;
else
{
num1[k++] = str1[i] - '';
had = true;
}
}
len1 = k;
k = ;
int bg = ;
for(int i = ; i < len_str2; i ++)
if (str2[i] != '')
{
bg = i;
break;
}
for (int i = len_str2 - ; i >= bg; i --)
num2[k++] = str2[i] - '';
len2 = k;
} bool cmp()
{
if (len2 > len3)
return false;
else if(len3 > len2)
{
if (num3[len3 - ] == )
return false;
return true;
}
else
{
for (int i = len2 - ; i >= ; i --)
{
if (num2[i] > num3[i])
return false;
if (num2[i] < num3[i])
return true;
}
}
return true;
} bool cmp_input()
{
if (len2 == && num2[] == )
return false;
if (len1 < len2)
return false;
if (len1 == len2)
{
for (int i = ; i < len1; i ++)
{
if (num1[i] > num2[len2 - i -])
return true;
if (num1[i] < num2[len2 - i - ])
return false;
}
}
return true;
} void red()
{
int reduce_num = ;
if (cmp())
{
get_num_pos += len3;
do
{
had_red = true;
int up = ;
for (int i = ; i < len3; i ++)
{
num3[i] = num3[i] - num2[i] - up;
if (num3[i] < )
{
num3[i] += ;
up = ;
}
else up = ;
}
int i;
for (i = len3 - ; i >= ; i --)
if (num3[i])
{
len3 = i + ;
break;
}
if (i < )
len3 = ;
reduce_num ++;
}while(cmp());
quo[len_quo++] = reduce_num;
int k = ;
for (int i = len3 - ; i >= ; i --)
{
res[k ++] = num3[i];
num3[i] = ;
}
len_res = len3;
if(cpt())
red();
else return;
}
else
{
if (had_red)
quo[len_quo ++] = ;
if (len3 == && num3[] == )
{
len3 = ;
get_num_pos ++;
}
if (get_num3())
red();
}
return;
} void output()
{
int i, j;
if (len_quo == )
len_quo = ;
if (len_res == )
len_res = ;
if (ope[] == '/')
{
for (int i = ; i < len_quo; i ++)
printf("%d", quo[i]);
puts("");
}
else if (ope[] == '%')
{
for (i = ; i < len_res; i ++)
printf("%d", res[i]);
puts("");
}
return;
} int main()
{
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
while (cin >> str1 >> ope >> str2)
{
had_red = false;
len_quo = ;
len_res = ;
len3 = ;
get_num_pos = ;
change();
if (cmp_input())
red();
else
for (int i = ; i < len1; i ++)
res[len_res++] = num1[i];
output();
} return ;
}
此题附上几组数据：
input：
8947186453786576673428174634 / 2147483647
1672563736 / 176317
17673764 / 74376
178226322222245124732648484 % 8276424
24969 / 123
100100 / 10
0 / 123
1002 % 10
1324211111111111111 / 456679284
21474836447 / 2147483647
output：
4166358363792735634
9486
237
3883828
203
10010
0
2
2899652245
9