曾彪彪的个人博客 -- 高精度除法

高精度除法计算，需要使用到高精度减法和乘法，代码如下：
```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)