【算法专题】高精度之压位

高精度之压位

当数据过大时，此时long long存储不下，因此需要使用vector或者数组存储，然后计算。

一般vector或者数组中每个数据都是一个int，如果每个位置只是存储0~9一位数字的话，比较浪费空间，并且计算也会变慢。因此可以让每个位置存储连续的多位数字，这被称作压位。

这里以压4位为例，也就是说：vector或者数组中每个位置存储四个连续的数字。

1. 基本高精度运算

关于基本高精度计算可以参考：高精度运算

2. 高精度压位运算

压位和不压位的高精度计算存在三点不同点（以下提到的压位都是压4位）：

（1）存储：不压位的话，vector或者数组中每个数据是0~9；压位以后，每个数据是0~9999。

（2）计算过程：不压位的话，除数和模数都是10；压位以后，除数和模数都是10000。

（3）输出：不压位的话，直接输出；压位的话，需要格式化输出，最高位直接输出即可，其他位都需要输出4位数字，不足的前面补零。

AcWing 791. 高精度加法

问题描述

问题链接：AcWing 791. 高精度加法

分析

加减法高精度其实可以压9位，这里为了演示，只压4位。

代码

C++

#include

#include

using namespace std;

const int N = 4, M = 1e4; // 压4位, 改这里注意同时需要该输出格式

vector add(vector &a, vector &b) {

vector c;

for (int i = 0, t = 0; i < a.size() || i < a.size() || t; i++) {

if (i < a.size()) t += a[i];

if (i < b.size()) t += b[i];

c.push_back(t % M);

t /= M;

}

return c;

}

void out(vector a) {

cout << a.back();

for (int i = a.size() - 2; i >= 0; i--) printf("%04d", a[i]);

cout << endl;

}

int main() {

string a, b;

cin >> a >> b;

vector A, B;

for (int i = a.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

A.push_back(stoi(a.substr(st, len)));

}

for (int i = b.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

B.push_back(stoi(b.substr(st, len)));

}

vector C = add(A, B);

out(C);

return 0;

}

AcWing 792. 高精度减法

问题描述

问题链接：AcWing 792. 高精度减法

分析

加减法高精度其实可以压9位，这里为了演示，只压4位。

代码

C++

#include

#include

using namespace std;

const int N = 4, M = 1e4; // 压4位, 改这里注意同时需要该输出格式

bool cmp(vector &a, vector &b) { // 比较a, b大小

if (a.size() != b.size()) return a.size() > b.size();

for (int i = a.size() - 1; ~i; i--)

if (a[i] != b[i])

return a[i] > b[i];

return true;

}

vector sub(vector &a, vector &b) {

vector 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 + M) % M);

if (t < 0) t = 1;

else t = 0;

}

while (c.size() > 1 && c.back() == 0) c.pop_back();

return c;

}

void out(vector a) {

cout << a.back();

for (int i = a.size() - 2; i >= 0; i--) printf("%04d", a[i]);

cout << endl;

}

int main() {

string a, b;

cin >> a >> b;

vector A, B;

for (int i = a.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

A.push_back(stoi(a.substr(st, len)));

}

for (int i = b.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

B.push_back(stoi(b.substr(st, len)));

}

if (!cmp(A, B)) {

cout << '-';

swap(A, B);

}

vector C = sub(A, B);

out(C);

return 0;

}

AcWing 793. 高精度乘法

问题描述

问题链接：AcWing 793. 高精度乘法

分析

因为b最大为10000，为了相乘不会超出int的范围，这里只能压4位。

代码

C++

#include

#include

using namespace std;

const int N = 4, M = 1e4; // 压4位, 改这里注意同时需要该输出格式

vector mul(vector &a, int b) {

vector c;

for (int i = 0, t = 0; i < a.size() || t; i++) {

if (i < a.size()) t += a[i] * b;

c.push_back(t % M);

t /= M;

}

while (c.size() > 1 && c.back() == 0) c.pop_back();

return c;

}

void out(vector a) {

printf("%d", a.back());

for (int i = a.size() - 2; i >= 0; i--) printf("%04d", a[i]);

cout << endl;

}

int main() {

string a;

int b;

cin >> a >> b;

vector A;

for(int i = a.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

A.push_back(stoi(a.substr(st, len)));

}

vector C = mul(A, b);

out(C);

return 0;

}

AcWing 794. 高精度除法

问题描述

问题链接：AcWing 794. 高精度除法

分析

演示压4位。

代码

C++

#include

#include

#include

using namespace std;

const int N = 4, M = 1e4; // 压4位, 改这里注意同时需要该输出格式

vector div(vector a, int b, int &r) {

vector c;

for (int i = a.size() - 1; i >= 0; i--) {

r = r * M + 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;

}

void out(vector a) {

printf("%d", a.back());

for (int i = a.size() - 2; i >= 0; i--) printf("%04d", a[i]);

cout << endl;

}

int main() {

string a;

int b;

cin >> a >> b;

vector A;

for(int i = a.size() - 1; i >= 0; i -= N) {

int st = max(0, i - N + 1), len = i - st + 1;

A.push_back(stoi(a.substr(st, len)));

}

int r = 0;

vector C = div(A, b, r);

out(C);

cout << r << endl;

return 0;

}