曾彪彪的个人网站
首页
文章列表
>>
文章详情
高精度除法
作者:
曾彪彪
日期:
2025-06-27 02:47:21
阅读(59)
分类:
Algorithm
高精度除法计算,需要使用到高精度减法和乘法,代码如下: ```c++ /** start time: 8:45 End time: Type: simulator Solution: - string divide string - if b==0 return error - if a<b return {0, b} - try to execute remainder/b, using multiple value to find out the quotient, to improve the efficient, we should binary search to find out the factor - test case: - 99999 9999 - 9999 9999 - 99999 9 - 1 1 - 0 0 - 789 98789 - 99999 0 first submit score: 100 cause: **/ #include <bits/stdc++.h> using namespace std; string multiple(string a, string b) { vector<int> result(a.size() + b.size(), 0); for (int i = a.size() - 1; i >= 0; i--) { for (int j = b.size() - 1; j >= 0; j--) { int v = result[i + j + 1] + (a[i] - '0') * (b[j] - '0'); result[i + j + 1] = v % 10; result[i + j] += v / 10; } } int start = 0; while (result[start] == 0) { start++; } string ans = ""; for (int i = start; i < result.size(); i++) { ans.push_back('0' + result[i]); } return ans.empty() ? "0" : ans; } string substract(string a, string b) { vector<int> result(a.size(), 0); b = string(a.size() - b.size(), '0') + b; int carry = 0; for (int i = a.size() - 1; i >= 0; i--) { int v = (a[i] - '0') - (b[i] - '0') - carry; if (v < 0) { v += 10; carry = 1; } else { carry = 0; } result[i] = v; } int start = 0; while (result[start] == 0) { start++; } string ans = ""; for (int i = start; i < result.size(); i++) { ans.push_back(result[i] + '0'); } return ans.empty() ? "0" : ans; } bool lessThan(string a, string b) { if (a.size() != b.size()) { return a.size() < b.size(); } return a < b; } pair<string, string> divide(string a, string b) { if (b == "0") { return {"error", "error"}; } if (lessThan(a, b)) { return {"0", a}; } if (a == b) { return {"1", "0"}; } string remainder = ""; string ans = ""; string quotient; for (int i = 0; i < a.size(); i++) { if (remainder == "0") { remainder = ""; } remainder.push_back(a[i]); if (lessThan(remainder, b)) { ans.push_back('0'); continue; } int low = 0, high = 9; while (low <= high) { int mid = (low + high) / 2; string product = multiple(b, to_string(mid)); if (lessThan(remainder, product)) { high = mid - 1; } else { string diff = substract(remainder, product); if (lessThan(diff, b)) { quotient = to_string(mid); remainder = substract(remainder, product); ans.append(quotient); break; } low = mid + 1; } } } while (ans[0] == '0' && ans.size() > 1) { ans = ans.substr(1); } while (remainder[0] == '0' && remainder.size() > 1) { remainder = remainder.substr(1); } return {ans, remainder}; } int main() { // freopen("C:/Users/zengsam/Downloads/P1042_2.in", "r", stdin); string a, b; cin >> a >> b; // pair ans = divide(a, b); // cout << ans.first << " " << ans.second << endl; cout << multiple(a, b) << endl; return 0; } ```
评论(0)
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)
提交
评论(必填)
名称(必填)
联系方式(可选)
验证码(必填)