高精度X高精度加法、减法、乘法
高精度X普通精度 乘法
高精度X普通精度 除法
目录
高精度X高精度 加法
题目
要点
- t 存储之前的部分位乘积和
- 每次取个位数进入 c
- 然后抛弃个位数
- 存在 t 没在 a 数位次数内处理完的情况,要补充处理
- 加法是唯一一个不需要处理前导零的
- 加法是唯二需要进一步处理 t 的
- a的位数要大于b等于b的位数
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> a, b;
string sa, sb;
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 % 10);
return c;
}
int main()
{
cin >> sa >> sb;
for(int i = sa.size()-1; i >= 0; i--)
a.push_back(sa[i] - '0');
for(int i = sb.size()-1; i >= 0; i--)
b.push_back(sb[i] - '0');
a = add(a, b);
for(int i = a.size()-1; i >= 0; i--)
cout << a[i];
return 0;
}
高精度X高精度 减法
题目
要点
- 注意要编写 cmp函数 使得 被减数大于减数
- 定义 t 计算开始表示之前的借位影响,中间表示不借位结果,最后表示当前借位对之后的影响
- t < 0证明借位
- (t+10)%10,自动借位,取最终结果
- 需要处理前导零
- a的位数要大于b等于b的位数
代码
#include <bits/stdc++.h>
using namespace std;
string sa, sb;
vector<int> a, b;
bool cmp()
{
if(a.size() != b.size()) return a.size() > b.size();
return sa >= sb; //注意这里必须取等,不然0就变成-0了
}
vector<int> sub(vector<int>& a, vector<int>& b)
{
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) % 10);
if(t < 0) t = -1;
else t = 0;
}
while(c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
int main()
{
cin >> sa >> sb;
for(int i = sa.size()-1; i >= 0; i--)
a.push_back(sa[i] - '0');
for(int i = sb.size()-1; i >= 0; i--)
b.push_back(sb[i] - '0');
if(cmp())
{
auto c = sub(a, b);
for(int i = c.size()-1; i >= 0; i--)
cout << c[i];
}
else
{
auto c = sub(b, a);
cout << '-';
for(int i = c.size()-1; i >= 0; i--)
cout << c[i];
}
return 0;
}
高精度X普通精度 乘法
题目
要点
- 需要处理前导零
- 乘法是唯二需要进一步处理 t 的
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> a;
int b;
string sa;
vector<int> mul(vector<int>& a, int b)
{
vector<int> c;
int t = 0;
for(int i = 0; i < a.size(); i++)
{
t += a[i] * b;
c.push_back(t % 10);;
t /= 10;
}
while(t)
{
c.push_back(t % 10);;
t /= 10;
}
while(c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
int main()
{
cin >> sa >> b;
for(int i = sa.size()-1; i >= 0; i--)
a.push_back(sa[i] - '0');
auto c = mul(a, b);
for(int i = c.size()-1; i >= 0; i--)
cout << c[i];
return 0;
}
高精度X高精度 乘法
要点
- 提前开 c,存储 a b各位相乘的结果,根据下标之和顺序放置;开得足够大同时可以免处理 t
- 计算是 c 的内部计算,思想不变
- 需要处理前导零
代码
#include <bits/stdc++.h>
using namespace std;
vector<int> a, b;
string sa, sb;
vector<int> mul(vector<int>& a, vector<int>& b)
{
vector<int> c(a.size() + b.size(), 0); //多开不要紧,后面有前导零处理
for(int i = 0; i < a.size(); i++)
for(int j = 0; j < b.size(); j++)
c[i+j] += a[i] * b[j];
int t = 0;
for(int i = 0; i < c.size(); i++) //不用进一步处理t,因为 c 的大小足够大
{
t += c[i];
c[i] = t % 10;
t /= 10;
}
while(c.size() > 1 && c.back() == 0) c.pop_back();
return c;
}
int main()
{
cin >> sa >> sb;
for(int i = sa.size()-1; i >= 0; i--)
a.push_back(sa[i] - '0');
for(int i = sb.size()-1; i >= 0; i--)
b.push_back(sb[i] - '0');
auto c = mul(a, b);
for(int i = c.size()-1; i >= 0; i--)
cout << c[i];
return 0;
}
高精度X普通精度 除法
题目
要点
- 存储统一,还是从低位到高位
- 定义 r 表示 上一位计算的余数,参与计算时需要 * 10
- 但是计算是从高位到低位,所以 c 也是从高位到低位,所以需要 reverse
- 需要除去前导零
代码
#include <bits/stdc++.h>
using namespace std;
string sa;
vector<int> a;
int b;
vector<int> div(vector<int>& a, int b, int& r)
{
vector<int> c;
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()
{
cin >> sa >> b;
for(int i = sa.size()-1; i >= 0; i--)
a.push_back(sa[i] - '0');
int r = 0;
auto c = div(a, b, r);
for(int i = c.size()-1; i >= 0; i--)
cout << c[i];
cout << '\n' << r;
return 0;
}