大數運算

大數運算

#include <bits/stdc++.h>
using namespace std;

vector<int> add(const vector<int>& A, const vector<int>& B);
vector<int> sub(const vector<int>& A, const vector<int>& B);
vector<int> mult(const vector<int>& A, const vector<int>& B);
vector<int> div(const vector<int>& A, const vector<int>& B);
int cmp(const vector<int>& A, const vector<int>& B);
vector<int> s2v(const string& num);
string v2s(const vector<int>& vec);

vector<int> add(const vector<int>& A, const vector<int>& B) {//O(n)
    vector<int> result;
    int carry = 0, i = A.size() - 1, j = B.size() - 1;

    while (i >= 0 || j >= 0 || carry > 0) {
        int sum = carry + (i >= 0 ? A[i--] : 0) + (j >= 0 ? B[j--] : 0);
        result.push_back(sum % 10);
        carry = sum / 10;
    }
    reverse(result.begin(), result.end());
    return result;
}

vector<int> sub(const vector<int>& A, const vector<int>& B) { // O(n)
    vector<int> result;
    int borrow = 0, i = A.size() - 1, j = B.size() - 1;

    while (i >= 0) {
        int diff = A[i--] - (j >= 0 ? B[j--] : 0) - borrow;
        if (diff < 0) diff += 10, borrow = 1;
        else borrow = 0;
        result.push_back(diff);
    }
    while (result.size() > 1 && result.back() == 0) result.pop_back();
    reverse(result.begin(), result.end());
    return result;
}

vector<int> mult(const vector<int>& A, const vector<int>& B) { // O(n^2)
    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 mul = A[i] * B[j] + result[i + j + 1];
            result[i + j + 1] = mul % 10;
            result[i + j] += mul / 10;
        }
    }
    while (result.size() > 1 && result[0] == 0) result.erase(result.begin());
    return result;
}

int cmp(const vector<int>& A, const vector<int>& B) { // O(n)
    if (A.size() != B.size())
        return A.size() < B.size() ? -1 : 1;

    for (int i = 0; i < A.size(); i++) {
        if (A[i] != B[i])
            return A[i] < B[i] ? -1 : 1;
    }
    return 0; // A == B
}

vector<int> div(const vector<int>& A, const vector<int>& B) { // O(n^2)
    if (B == vector<int>{0}) throw invalid_argument("Division by zero");
    vector<int> result, current;

    for (int digit : A) {
        current.push_back(digit);
        while (current.size() > 1 && current[0] == 0) current.erase(current.begin());
        int quotient = 0;
        while (cmp(current, B) >= 0) {
            current = sub(current, B);
            quotient++;
        }
        result.push_back(quotient);
    }
    while (result.size() > 1 && result[0] == 0) result.erase(result.begin());
    return result.empty() ? vector<int>{0} : result;
}

vector<int> s2v(const string& num) { // O(n)
    vector<int> result(num.begin(), num.end());
    for (auto& c : result) c -= '0';
    return result;
}

string v2s(const vector<int>& vec) { // O(n)
    string result(vec.size(), '0');
    for (size_t i = 0; i < vec.size(); i++) result[i] += vec[i];
    return result;
}

int main() {
    string num1;cin>>num1;
    string num2;cin>>num2;

    cout << v2s(div(s2v(num1),s2v(num2))) << endl;
    return 0;
}