Algorithm16 高精度&大数运算
[TOC]
高精度 & 大数运算
（一）高精度除法-高精度除低精度 < 高精度加法 < 高精度乘法 < 高精度减法 < 高精度除法-高精度除高精度
（二）语言：python，Java的四则运算自带高精度；C/C++需要利用字符串/字符数组来读取大数并开数组存放然后通过模拟竖式运算来计算。
大数加法
https://www.luogu.com.cn/problem/P1601
1、读入用字符数组读入。
2、做加法通过考虑进位位。
3、输出的时候特判进位位是否需要单独输出
#include <iostream>
using namespace std;
#define maxn 100005
char sa[maxn], sb[maxn];
int a[maxn], b[maxn], ans[maxn], lena, lenb ,lenans, ap;
#include <cmath>
#include <string.h>
void read() {
lena = strlen(sa);lenb = strlen(sb);
lenans = max(lena, lenb);
for (int i = 0; i < lena; ++i) a[i] = sa[lena-1-i] - '0';
for (int i = 0; i < lenb; ++i) b[i] = sb[lenb-1-i] - '0';
}
void add(int a[], int b[]) {
for (int i = 0; i < lenans; ++i) {
ans[i] = a[i]+b[i]+ap;
ap = ans[i]/10;
ans[i]%=10;
}
}
void write() {
if (ap) printf("%d", ap);
for (int i = lenans-1; i >= 0; --i) printf("%d", ans[i]);
}
int main() {
scanf("%s%s", sa, sb);
read();
add(a, b);
write();
return 0;
}
大数减法
https://www.luogu.com.cn/problem/P2142
1、也是用一个辅助ap来进行修正，对竖型运算的过程进行修正
2、对于做完减法得到负数的情况，可以通过对输入string进行判断大小，然后如果被减数小的话，那就直接后面的数减前面的数，然后再添个负号即可。
#include <iostream>
using namespace std;
#define maxn 100005
//char sa[maxn], sb[maxn];
string sa, sb;
int a[maxn], b[maxn], ans[maxn], lena, lenb , lenans, ap, isneg;
#include <cmath>
#include <string.h>
void read() {
// lena = strlen(sa);lenb = strlen(sb);
lena = sa.length();lenb = sb.length();
lenans = max(lena, lenb);
for (int i = 0; i < lena; ++i) a[i] = sa[lena-1-i] - '0';
for (int i = 0; i < lenb; ++i) b[i] = sb[lenb-1-i] - '0';
}
void sub(int a[], int b[]) {
for (int i = 0; i < lenans; ++i) {
ans[i] = a[i]+ap>=b[i]?a[i]+ap-b[i]:a[i]+ap+10-b[i];
ap = a[i]+ap>=b[i]?0:-1;
}
}
void write() {
if (isneg == 1) printf("-");
int flag = 1;
for (int i = lenans-1; i >= 0; --i)
if (flag && !ans[i]) {flag = 0;continue;}
else {flag = 0; printf("%d", ans[i]);}
}
int main() {
// scanf("%s%s", sa, sb);
cin>>sa>>sb;
read();
if (sa.size() > sb.size() || (sa.size() == sb.size() && sa > sb)) sub(a, b);
else {isneg = 1;sub(b, a);}
write();
return 0;
}
大数乘法
https://www.luogu.com.cn/problem/P1303
#include <iostream>
using namespace std;
#define maxn 100005
//char sa[maxn], sb[maxn];
string sa, sb;
int a[maxn], b[maxn], ans[maxn], lena, lenb , lenans, ap, isneg;
#include <cmath>
#include <string.h>
void read() {
lena = sa.length();lenb = sb.length();
lenans = lena+lenb;
for (int i = 0; i < lena; ++i) a[i] = sa[lena-1-i] - '0';
for (int i = 0; i < lenb; ++i) b[i] = sb[lenb-1-i] - '0';
}
void mul(int a[], int b[]) {
for (int i = 0; i < lenb; ++i)
for (int j = 0; j < lena; ++j)
ans[i+j] += b[i]*a[j];
for (int i = 0; i < lenans; ++i) {
ans[i+1] += ans[i]/10;
ans[i] %= 10;
}
}
void write() {
int flag = 1;
for (int i = lenans-1; i >= 0; --i)
if (flag && !ans[i]) {flag = 0;continue;}
else {flag = 0; printf("%d", ans[i]);}
}
int main() {
// scanf("%s%s", sa, sb);
cin>>sa>>sb;
if ((sa.length() == 1 && sa[0] == '0') || (sb.length() == 1 && sb[0] == '0')) {printf("0");return 0;}
read();
mul(a, b);
write();
return 0;
}
大数除法-高精度/低精度
https://www.luogu.com.cn/problem/P1480
#include <iostream>
using namespace std;
#define maxn 100005
//char sa[maxn], sb[maxn];
string sa;
typedef long long ll;
ll a[maxn], b, ans[maxn], lena, lenb , lenans, ap, isneg;
#include <cmath>
#include <string.h>
void read() {
// lena = strlen(sa);lenb = strlen(sb);
lena = sa.length();
lenans = lena;
for (int i = 0; i < lena; ++i) a[i] = sa[i] - '0';
}
void div(ll a[]) {
for (int i = 0; i < lenans-1; ++i) {
ans[i] = a[i]/b;
a[i+1] += (a[i]%b)*10;
}
ans[lenans-1] = a[lenans-1]/b;
}
void write() {
int flag = 1;
for (int i = 0; i < lenans; ++i)
if (flag && !ans[i]) continue;
else {flag = 0; printf("%d", ans[i]);}
}
int main() {
// scanf("%s%s", sa, sb);
cin>>sa>>b;
read();
div(a);
write();
return 0;
}
C/C++ 模版
python 模版
注意：python中在乘法运算中区分//和/的区别，//是做除法，然后向下取整；而/也是做除法，只是保留若干位小数。
print(int(input())+int(input()))
print(int(input())-int(input()))
print(int(input())*int(input()))
print(int(input())//int(input()))