高精度类型主要有以下四种
- 高精度加法(位数 $10^6$)
- 高精度减法 ($10^6$)
- 高精度乘法(
len
$10^6$,大的数 $\times$ 小的数) - 高精度除法(高精度除低精度)
$1$ . 高精度加法
高精度加法相当于小学的竖式加法
设 $a$ 与 $b$ 分别为 $123$ 和 $89$
竖式算法过程如下:
$123$ % $10$ 为 $3$ 所以各位为 $3$ + $b$ % $10$
$b$ 等于 $89$ ,$89$ % $10$ 为 $9$,所以 $3$ 和 $9$ 相加
$3$ 与 $9$ 加起来结果为 $12$,那么不能将结果写为 $12$ 怎么办呢?
那么我们需要向十位进 $1$ ,于是个位写 $1$
接下来我们取十位,取十位公式为 a/10%10
$a$ 为 $123$ , $123$ $\div$ $10$ 为 $12$,$12$ % $10$ 的余数是 $2$ ,得出 $123$ 的余数为 $2$,所以 $2$ 写在个位上
接下来拆分 $b$ 的十位,$b$ 为 $89$ ,$89$ $\div$ $10$ 为 $8$,$8$ % $10$ 为 $8$ ,所以得出 $b$ 的十位为 $8$
$b$ 的十位 $8$ 与 $a$ 的十位 $2$ 相加,得 $10$ ,再加上个位进来的 $1$ 为 $11$ 写 $1$ 向百位进 $1$,所以 $1$ 写在十位上
接下来拆分百位 , $b$ 没有百位怎么办?
写 $0$ 占位,$b$ 就变成了 $089$ ,算 $123$ 加 $089$
百位的计算公式为 b/100%10
,先来拆分 $a$ ,$a$ 等于 $123$ ,于是我们将 $123$ $\div$ $100$ 得出结果为 $1$ , $1$ % $10$ 也是 $1$ ,所以得出 $a$ 的百位为 $1$
接下来拆分 $b$ ,$b$ 等于 $089$,$b$ $\div$ $100$ 为 $0$ ,$0$ % $10$ 也是 $0$,加上十位进来的那个 $1$ 就是 $1+1+0$ 等于 $2$,所以 $2$ 写在百位上
最后将所有位数上的数合并起来,回顾一下,个位是 $2$,十位是 $1$,百位是 $2$ ,合并起来是 $212$ 我们的结果就算完了
代码
// 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 = 0;
for (int i = 0; i < A.size(); i ++ )
{
t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(t);
return C;
}
作者:yxc
链接:https://www.acwing.com/blog/content/277/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
$2$.高精度减法
如果 $a \geq b$ 那么直接算
如果 $b \geq a$ 那么算 $b-a$ 在前面加负号
$a$ 和 $b$ 都是 $\geq$ $0$ 的
完整代码
#include<bits/stdc++.h>
using namespace std;
bool cmp(vector<int>&A,vector<int>&B)
{
if(A.size()!=B.size())return A.size()>B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]>B[i];
return true;
}
vector<int>sub(vector<int>&A,vector<int>&B)
{
vector<int>C;
for(int i=0,t=0;i<A.size();i++){
t=A[i]-t;
if(i<B.size())t-=B[i];
C.push_back((t+10)%10);
if(t<0)t=1;
else t=0;
}
while(C.size()>1&&C.back()==0)C.pop_back();
return C;
}
void solve(){
string a,b;
vector<int>A,B;
cin>>a>>b;
for(int i=a.size()-1;i>=0;i--)A.push_back(a[i]-'0');
for(int i=b.size()-1;i>=0;i--)B.push_back(b[i]-'0');
vector<int>C;
if(cmp(A,B))C=sub(A,B);
else C=sub(B,A),cout<<'-';
for(int i=C.size()-1;i>=0;i-- )cout<<C[i];
cout<<endl;
}
int main()
{
solve();
return 0;
}
$3$ .高精度乘法
手算模拟:每个被乘数位与 $B$ 的整体进行相乘
完整代码
#include <iostream>
#include <vector>
using namespace std;
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
int b;
cin >> a >> b;
vector<int> A;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
auto C = mul(A, b);
for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39794/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
$4$.高精度除法
高精度除法就是求出商和余数,将上一位的余数 $\time $10$ 加上当前的位置,往答案里压入 $b$ 就可以了
代码如下
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> div(vector<int> &A, int b, int &r)
{
vector<int> C;
r = 0;
for (int i = A.size() - 1; i >= 0; i -- )
{
r = r * 10 + A[i];
C.push_back(r / b);
r %= b;
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}
int main()
{
string a;
vector<int> A;
int B;
cin >> a >> B;
for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
int r;
auto C = div(A, B, r);
for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
cout << endl << r << endl;
return 0;
}
作者:yxc
链接:https://www.acwing.com/activity/content/code/content/39795/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
orz我到现在都没学会过高精
其实就是模拟排竖式