acwing高精度算法模板

高精度算法是指能够处理超出计算机基本数据类型范围的数字运算问题的算法。常见的高精度算法有大整数加减乘除、高精度开方、高精度取模等。

以下是acwing的高精度算法模板：

1. 大整数加法

C++ 代码：

vector<int> add(vector<int> &A, vector<int> &B) {
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || i < B.size(); i++) {
if (i < A.size()) t += A[i];
if (i < B.size()) t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t) C.push_back(1);
return C;
}

2. 大整数减法

C++ 代码：

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;
}

3. 大整数乘法

C++ 代码：

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;
}
return C;
}

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++) {
int t = 0;
for (int j = 0; j < B.size() || t; j++) {
if (j < B.size()) t += A[i] * B[j];
t += C[i + j];
C[i + j] = t % 10;
t /= 10;
}
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

4. 大整数除法

C++ 代码：

int cmp(vector<int> &A, vector<int> &B) {
if (A.size() != B.size()) return A.size() < B.size() ? -1 : 1;
for (int i = A.size() - 1; i >= 0; i--) {
if (A[i] != B[i]) return A[i] < B[i] ? -1 : 1;
}
return 0;
}

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;
}

vector<int> div(vector<int> &A, vector<int> &B) {
vector<int> C;
for (int i = A.size() - 1; i >= 0; i--) {
C.insert(C.begin(), A[i]);
while (cmp(C, B) >= 0) {
vector<int> t = sub(C, B);
C = t;
}
}
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

5. 高精度开方

C++ 代码：

int cmp(vector<int> &A, vector<int> &B) {
if (A.size() != B.size()) return A.size() < B.size() ? -1 : 1;
for (int i = A.size() - 1; i >= 0; i--) {
if (A[i] != B[i]) return A[i] < B[i] ? -1 : 1;
}
return 0;
}

vector<int> sqrt(vector<int> &A) {
vector<int> C;
if (A.size() % 2 == 1) A.push_back(0);
for (int i = A.size() - 2; i >= 0; i -= 2) {
int res = 0;
for (int j = 9; j >= 0; j--) {
vector<int> t = mul(C, 20);
t.push_back(j * j);
if (cmp(t, A) <= 0) {
res = j;
C.push_back(j);
break;
}
}
}
reverse(C.begin(), C.end());
while (C.size() > 1 && C.back() == 0) C.pop_back();
return C;
}

6. 高精度取模

C++ 代码：

int mod(vector<int> &A, int b) {
int r = 0;
for (int i = A.size() - 1; i >= 0; i--) {
r = r * 10 + A[i];
r %= b;
}
return r;
}

vector<int> mod(vector<int> &A, vector<int> &B) {
vector<int> C;
for (int i = A.size() - 1; i >= 0; i--) {
C.insert(C.begin(), A[i]);
while (cmp(C, B) >= 0) {
vector<int> t = sub(C, B);
C = t;
}
}
return C;
}