高精度
高精度加法，高精度减法，高精度乘低精度，高精度除以低精度，大概平时用的最多的就是这四个，模板有两种（因为我现在不太会用vector，就用数组也写了个，23333）
高精度运算和人工手算差不多，就是模拟人工手算的过程，乘法有点不一样，在下面有提到，大致也是模拟运算
废话不多说，上模板
高精度加法
// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
if (A.size() < B.size()) return add(B, A); vector<int> C;
int t = ;
for (int i = ; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % );
t /= ;
} if (t) C.push_back(t);
return C;
}
高精度减法
// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
vector<int> C;
for (int i = , t = ; i < A.size(); i ++ )
{
t = A[i] - t;
if (i < B.size()) t -= B[i];
C.push_back((t + ) % );
if (t < ) t = ;
else t = ;
} while (C.size() > && C.back() == ) C.pop_back();
return C;
}
这里高精度减法对于A < B 的情况我们特判下输出个 - 就好了，模板第九行是比较巧的一步，因为我们减一位后 t 的取值范围是（-10，10）t 可能是正数也可能是负数，对于正数我们可以直接拿来用，对于负数要向前面一位进1，相当于把 t 加10，这里写成（t + 10）% 10 就能把两种情况写在一起了
高精度乘低精度
// C = A * b, A >= 0, b > 0
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = ;
for (int i = ; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % );
t /= ;
} return C;
}
乘法和我们人模拟的算有点差别，比如156 * 23 算第一位的时候直接拿6 * 23，然后再拿5 * 23 + 进位，以此类推
高精度除以低精度
// A / b = C ... r, A >= 0, b > 0
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = ;
for (int i = A.size() - ; i >= ; i -- )
{
r = r * + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > && C.back() == ) C.pop_back();
return C;
}
上面是用vector的模板，对于不会用vector的我，用数组写了个，呃呃呃呃....
高精度加法
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
int add(int a[], int b[]);
const int N = + ;
char x1[N], x2[N];
int a[N], b[N], c[N]; int main()
{
scanf("%s%s",x1,x2);
int len1 = strlen(x1), len2 = strlen(x2);
for(int i = len1 - , j = ; i >= ; i --, j ++)
a[j] = x1[i] - '';
for(int i = len2 - , j = ; i >= ; i --, j ++)
b[j] = x2[i] - ''; int id = add(a, b);
for(int i = id - ; i >= ; i --)
printf("%d",c[i]);
return ;
//add(a,b); } int add(int a[], int b[])
{
int mx = , id = ;
if(strlen(x1) >= strlen(x2)) mx = strlen(x1);
else mx = strlen(x2);
int t = ;
for(int i = ; i < mx; i ++)
{
c[id++] = (a[i] + b[i] + t) % ;
t = (a[i] + b[i] + t) / ;
}
if(t) c[id++] = t;
return id;
}
高精度减法
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
int mun(int a[], int b[]);
bool cmp(int a[], int b[]); //用来比较a,b谁大，判断是输出正数还是负数
const int N = + ;
char x[N], y[N];
int a[N], b[N], c[N]; int main()
{
scanf("%s%s",x,y);
int lena = strlen(x), lenb = strlen(y);
for(int i = lena - , j = ; i >= ; i --, j ++ ) a[j] = x[i] - '';
for(int i = lenb - , j = ; i >= ; i --, j ++ ) b[j] = y[i] - ''; if(cmp(a, b)) cout << "-";
int temp = mun(a, b);
for(int i = temp - ; i >= ; i -- )
printf("%d",c[i]);
return ;
} int mun(int a[], int b[])
{
if(cmp(a, b)) return (mun(b, a)); int t = , mx = max(strlen(x), strlen(y));
for(int i = ; i < mx; i ++ )
{
t = a[i] - b[i] + t;
c[i] = (t + ) % ;
if(t < ) t = -;
else t = ;
} int id = mx;
for(int i = mx - ; i > ; i --) //去除前导零
{
if(c[i] == ) id -- ;
else break;
}
return id; //id是数组c的长度
} bool cmp(int a[], int b[])
{
int mx = max(strlen(x), strlen(y));
for(int i = mx - ; i >= ; i -- )
{
if(a[i] > b[i]) return ;
if(a[i] < b[i]) return ;
}
return ;
}
高精度乘法
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std;
int mul(int a[], int b);
const int maxa = + ;
char x[maxa];
int a[maxa], c[maxa], b; int main()
{
scanf("%s%d",x,&b);
int lena = strlen(x);
for(int i = lena - , j = ; i >= ; i --, j ++ ) a[j] = x[i] - ''; int id = mul(a, b);
for(int i = id - ; i >= ; i -- )
cout << c[i];
return ;
} int mul(int a[], int b)
{
int t = , id = , lena = strlen(x);
for(int i = ; i < lena; i ++ )
{
t = a[i] * b + t;
c[id++] = t % ;
t = t / ;
}
if(t) c[id++] = t;
return id;
}
高精度除法
#include <iostream>
#include <cstring>
#include <cstdio> using namespace std;
int div(int b[], int k);
const int N = + ;
string a;
int b[N], c[N], k, t; //t是余数 int main()
{
cin >> a >> k;
for(int i = ; i < a.size(); i ++ ) b[i] = a[i] - ''; int id = div(b, k);
int q = ;
for(int i = ; i < id - ; i ++ )
if(c[i] == ) q ++ ;
else break;
for(int i = q; i < id; i ++ )
printf("%d",c[i]);
printf("\n%d",t);
return ;
} int div(int b[], int k)
{
int id = ;
for(int i = ; i < a.size(); i ++ )
{
t = t * + b[i];
c[id++] = t / k;
t %= k;
}
return id;
}
输出两行，第一行是商，第二行是余数