【C++】常见高精度计算模板
最近打算新开一个系列,由于博主的记忆力无限趋近于0,学过的基本是秒忘记。因此想到利用自己的博客给自己记录一下代码的模板,方便自己日后的查找使用。
由于博主大脑是混沌体系,所以就没有前后顺序了,想到啥就放上来啥。
最近遇到很多很多很多高精度计算的问题,虽然python一行解决,但是.....
大部分竞赛用不了python😅(虽然但是jvav其实也有高精,但是博主只会Hello World)
(由于禁止复制的策略,你可以点击在新标签页查看再复制!!!)
加法
纯模拟 时间复杂度O(n)
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; constexpr int MAXN = 1e3; string sum(string a, string b) { if (a.size() > b.size() || (a.size() == b.size() && a > b)) swap(a, b); vector<int> res(MAXN + 3, 0); int pos = 0; for (int i = a.size() - 1; i >= 0; i--) { res[pos++] = a[i] - '0'; } for (int i = b.size() - 1; i >= 0; i--) { res[b.size() - 1 - i] += b[i] - '0'; res[b.size() - i] += res[b.size() - 1 - i] / 10; res[b.size() - 1 - i] %= 10; } bool f = 0; string ans = ""; for (int i = MAXN; i >= 0; i--) { if (res[i] != 0) { f = 1; } if (f) ans += res[i] + '0'; } return ans == "" ? "0" : ans; } int main() { string a, b; cin >> a >> b; cout << sum(a, b) << endl; return 0; }

减法
纯模拟 时间复杂度O(n)
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; constexpr int MAXN = 1e3; string sub(string a, string b) { auto apos = a.find_first_not_of('0'); auto bpos = b.find_first_not_of('0'); if (apos != string::npos) a = a.substr(apos); if (bpos != string::npos) b = b.substr(bpos); bool mark = 0, f = 0; int pos = 0; vector<int> res(1e3 + 5, 0); if (a.size() < b.size() || (a.size() == b.size() && a < b)) { mark = 1; swap(a, b); } for (int i = a.size() - 1; i >= 0; i--) { res[pos++] += a[i] - '0'; } for (int i = b.size() - 1; i >= 0; i--) { if (res[b.size() - 1 - i] - (b[i] - '0') < 0) { res[b.size() - 1 - i] += 10; res[b.size() - i] -= 1; } res[b.size() - 1 - i] -= b[i] - '0'; } for (int i = b.size(); i <= MAXN; i++) { if (res[i] < 0) { res[i] += 10; res[i + 1] -= 1; } } string ans = mark ? "-" : ""; for (int i = MAXN; i >= 0; i--) { if (res[i] != 0) { f = 1; } if (f) ans += res[i] + '0'; } return (ans == "" || ans == "-") ? "0" : ans; } int main() { string a, b; cin >> a >> b; cout << sub(a, b) << endl; return 0; }

乘法
分为低精度×高精度和高精度×高精度两个版本。
(由于博主很笨,压位高精还没学会,这里没有提供。如果以后学会会补充上的...)
高精度×低精度
纯模拟 时间复杂度O(n)
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; string mul(string a, int b) { vector<int> res(a.size() + 10, 0); for (int i = a.size() - 1; i >= 0; i--) { res[a.size() - i - 1] = (a[i] - '0') * b; } for (int i = 0; i < res.size(); i++) { if (res[i] >= 10) { res[i + 1] += res[i] / 10; res[i] %= 10; } } while (res.size() > 1 && res.back() == 0) { res.pop_back(); } string ans = ""; for (int i = res.size() - 1; i >= 0; i--) { ans += res[i] + '0'; } return ans; } int main() { string a; int b; cin >> a >> b; cout << mul(a, b) << endl; return 0; }

高精度×高精度
抄袭模板 时间复杂度O(n²)
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; constexpr int MAXN = 1e3; string multi(string& a, string& b) { vector<int> na(MAXN + 3), nb(MAXN + 3), res(MAXN + 5, 0); bool f = 0; for (int i = a.size() - 1; i >= 0; i--) { na[a.size() - 1 - i] = a[i] - '0'; } for (int i = b.size() - 1; i >= 0; i--) { nb[b.size() - 1 - i] = b[i] - '0'; } for (int i = 0; i <= MAXN; i++) { for (int j = 0; j <= i; j++) res[i] += na[j] * nb[i - j]; if (res[i] >= 10) { res[i + 1] += res[i] / 10; res[i] %= 10; } } string ans = ""; for (int i = MAXN; i >= 0; i--) { if (res[i] != 0) f = 1; if (f) ans += res[i] + '0'; } return ans == "" ? "0" : ans; } int main() { string a, b; cin >> a >> b; cout << multi(a, b) << endl; return 0; }

除法
和乘法一致,分为高精度÷低精度和高精度÷高精度两个版本。
高精度÷低精度
纯模拟 时间复杂度O(n)
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; string div(string& a, int b) { string res = ""; long long remain = 0; for (auto& i : a) { remain = remain * 10 + i - '0'; res += remain / b + '0'; remain %= b; } auto it = res.find_first_not_of('0'); if (it != string::npos) return res.substr(it); else return "0"; } int main() { string a; int b; cin >> a >> b; cout << div(a, b) << endl; return 0; }

高精度÷高精度
代码完全抄袭自oi-wiki。时间复杂度为O(n^2)
#include <iostream> #include <algorithm> #include <vector> #include <string> using namespace std; constexpr int MAXN = 1e3; bool candiv(vector<int>& a, vector<int>& b, int apos, int blen) { if (a[apos + blen] != 0) return 1; for (int i = blen - 1; i >= 0; i--) { if (a[apos + i] > b[i]) return 1; if (a[apos + i] < b[i]) return 0; } return 1; } string div(string& x, string& y) { if (y == "0") return "-1"; if (y == "1") return x; vector<int> a(MAXN + 5), b(MAXN + 5), res(MAXN + 5); for (int i = x.size() - 1; i >= 0; i--) a[x.size() - 1 - i] = x[i] - '0'; for (int i = y.size() - 1; i >= 0; i--) b[y.size() - 1 - i] = y[i] - '0'; int len = x.size() - y.size(); for (int i = x.size() - y.size(); i >= 0; i--) { while (candiv(a, b, i, y.size())) { res[i]++; for (int j = 0; j < y.size(); j++) { if (a[i + j] < b[j]) { a[i + j + 1]--; a[i + j] += 10; } a[i + j] -= b[j]; } } } string ans = ""; bool f = 0; for (int i = MAXN; i >= 0; i--) { if (res[i] != 0) f = 1; if (f) ans += res[i] + '0'; } return ans; } int main() { string a, b; cin >> a >> b; if (a.size() < b.size() || (a.size() == b.size() && a < b)) { cout << "0" << endl; return 0; } cout << div(a, b) << endl; return 0; }

高精度快速幂
不知道放哪里。就先放在这里了🤓
代码完全抄袭自oi-wiki
题目:[NOIP 2003 普及组] 麦森数(https://www.luogu.com.cn/problem/P1045)
#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; vector<int> a(505), b(505), tmp(505); void multi(vector<int>& x, vector<int>& y) { tmp = vector<int>(505, 0); for (int i = 1; i <= x[0]; i++) { for (int j = 1; j <= y[0]; j++) { if (i + j - 1 > 500) continue; tmp[i + j - 1] += x[i] * y[j]; tmp[i + j] += tmp[i + j - 1] / 10; tmp[i + j - 1] %= 10; tmp[0] = i + j; } } b = tmp; } // kasumi 也是快速幂 void kasumi(int n) { if (n == 1) { b = a; return; } kasumi(n / 2); multi(b, b); if (n % 2 != 0) multi(b, a); } int main() { ios::sync_with_stdio(0); cout.tie(0); int p; cin >> p; int res = p * log10(2) + 1; cout << res; a[0] = 1, b[0] = 1; a[1] = 2, b[1] = 1; kasumi(p); for (int i = 500; i >= 1; i--) { if (i % 50 == 0) cout << endl; if (i == 1) { cout << b[i] - 1 << endl; break; } cout << b[i]; } return 0; }
目前就这些内容。希望我以后遗忘可以慢一点。。。同时如果这也能帮到你,我很荣幸。真的。。
版权声明:
作者:Toms Project
链接:https://blog.projectoms.com/pages/1495.html
来源:Toms Project 官方博客
文章版权归作者所有,未经允许请勿转载。


Toms Project
TPBlog 评论已经支持显示IP所属网络!!!
快来评论试试吧