Zerojudge a021：大數運算 & d427：大數根號

Zerojudge a021 & d427

a021：大數運算

加法：用兩個 $\text{vector}$ 存，若超過 $10^9$ 則進位。

減法：先比較 $\text{vector}$ 的大小，如果 $v_1<v_2$ 先輸出 $`-'$ 再交換，中間相減如果小於 $0$ 要借位，最後把多餘的 $0$ 去掉。

乘法：把 $v_1$ 第 $i$ 位和 $v_2$ 第 $j$ 位相乘，取餘數放在第 $i+j$ 位，最後處理多出的數。

除法：把被除數一位一位加上去，去比較比除數的幾倍大，輸出倍數然後扣掉，除數倍數可以先存。

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
#define vint vector<int>
using namespace std;
const int mod = 1000000000;
bool bigger (vint v1, vint v2) {
    if (v1.size() > v2.size() || v1 == v2)
        return 1;
    if (v1.size() < v2.size())
        return 0;
    for (int i = v1.size() - 1; i >= 0; i--) {
        if (v1[i] > v2[i])
            return 1;
        if (v1[i] < v2[i])
            return 0;
    }
}
vint ItoV (int n) {
    vint re;
    re.push_back (n);
    return re;
}
vint StoV (string str) {
    vint re;
    int num = 0, now = 0, ten = 1;
    for (int i = str.length() - 1; i >= 0; i--) {
        num += (str[i] - '0') * ten;
        now++;
        if (now == 9)
            now = 0, ten = 1, re.push_back (num), num = 0;
        else
            ten *= 10;
    }
    if (num)
        re.push_back (num);
    return re;
}
void out (vint vec) {
    cout << vec[vec.size() - 1];
    for (int i = vec.size() - 2; i >= 0; i--) {
        int len = 0, num = vec[i];
        do {
            len++;
            num /= 10;
        } while (num);
        len = 9 - len;
        while (len--)
            cout << '0';
        cout << vec[i];
    }
    cout << '\n';
}
vint add (vint v1, vint v2, bool is) {
    vint re;
    long long num = 0;
    for (int i = 0;; i++) {
        if (i >= v1.size() && i >= v2.size() && num == 0)
            break;
        if (i < v1.size())
            num += v1[i];
        if (i < v2.size())
            num += v2[i];
        re.push_back (num % mod);
        num /= mod;
    }
    if (is == 1)
        out (re);
    else
        return re;
}
vint sub (vint v1, vint v2, bool is) {
    if (is == 1 && bigger (v1, v2) == 0) {
        cout << '-';
        vint temp = v2;
        v2 = v1, v1 = temp;
    }
    vint re;
    long long num = 0;
    for (int i = 0; i < v1.size(); i++) {
        num = v1[i] - num;
        if (i < v2.size())
            num -= v2[i];
        if (num >= 0)
            re.push_back (num), num = 0;
        else
            re.push_back (mod + num), num = 1;
    }
    int sum = 0;
    for (int i = re.size() - 1; i >= 0; i--) {
        if (re[i] == 0)
            sum++;
        else
            break;
    }
    re.resize (re.size() - sum);
    if (re.size() == 0)
        re.push_back (0);
    if (is == 1)
        out (re);
    else
        return re;
}
vint mult (vint v1, vint v2, bool is) {
    if ( ( (v1.size() == 1 && v1[0] == 0) || (v2.size() == 1 && v2[0] == 0))) {
        if (is == 1) {
            cout << "0\n";
            return ItoV (0);
        } else
            return ItoV (0);
    }
    long long num = 0;
    vint re;
    for (int i = 0; i < v1.size(); i++) {
        for (int j = 0; j < v2.size(); j++) {
            num += (long long) v1[i] * v2[j];
            if (i + j >= re.size())
                re.push_back (0);
            num += re[i + j];
            re[i + j] = num % mod;
            num /= mod;
        }
        int now = i + v2.size();
        while (num) {
            if (now >= re.size())
                re.push_back (0);
            num += re[now];
            re[now] = num % mod;
            num /= mod;
            now++;
        }
    }
    int now = v1.size() + v2.size() - 1;
    while (num) {
        if (now >= re.size())
            re.push_back (0);
        num += re[now];
        re[now] = num % mod;
        num /= mod;
        now++;
    }
    if (is == 1)
        out (re);
    else
        return re;
}
void divi (string str, vint v) {
    if (bigger (StoV (str), v) == 0) {
        cout << "0\n";
        return;
    }
    vint vec = ItoV (0);
    vint vv[10];
    for (int i = 0; i < 10; i++)
        vv[i] = mult (v, ItoV (i), 0);
    bool is = 0;
    for (int k = 0; k < str.length(); k++) {
        vec = add (mult (vec, ItoV (10), 0), ItoV (str[k] - '0'), 0);
        if (is == 0) {
            if (bigger (vec, v) == 1) {
                for (int i = 9; i >= 0; i--)
                    if (bigger (vec, vv[i]) == 1) {
                        cout << i;
                        vec = sub (vec, vv[i], 0);
                        break;
                    }
                is = 1;
            }
        } else {
            for (int i = 9; i >= 0; i--)
                if (bigger (vec, vv[i]) == 1) {
                    cout << i;
                    vec = sub (vec, vv[i], 0);
                    break;
                }
        }
    }
    cout << '\n';
}
int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    string str1, str2, c;
    cin >> str1 >> c >> str2;
    if (c == "+")
        add (StoV (str1), StoV (str2), 1);
    if (c == "-")
        sub (StoV (str1), StoV (str2), 1);
    if (c == "*")
        mult (StoV (str1), StoV (str2), 1);
    if (c == "/")
        divi (str1, StoV (str2));
}

d427：大數根號

原理可見維基百科

首先先處理整數部分，再處理小數

然後乘法的地方寫錯了，不過因為 $\text{vec2}$ 的長度都只用到 $1$，所以沒差

#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
using namespace std;
const int mod = 1000000000;
bool bigger (vector<int>vec1, vector<int>vec2) {
    if (vec2.size() > vec1.size() || vec1 == vec2)
        return 0;
    if (vec1.size() > vec2.size())
        return 1;
    for (int i = vec1.size() - 1; i >= 0; i--) {
        if (vec1[i] > vec2[i])
            return 1;
        if (vec1[i] < vec2[i])
            return 0;
    }
}
vector<int>plu (vector<int>vec1, vector<int>vec2) {
    long long num = 0;
    vector<int>re;
    for (int i = 0;; i++) {
        if (i >= vec1.size() && i >= vec2.size() && num == 0)
            break;
        if (i < vec1.size())
            num += vec1[i];
        if (i < vec2.size())
            num += vec2[i];
        re.push_back (num % mod);
        num /= mod;
    }
    return re;
}
vector<int>dec (vector<int>vec1, vector<int>vec2) {
    long long num = 0;
    int sum = 0;
    vector<int>re;
    for (int i = 0; i < vec1.size(); i++) {
        num = vec1[i] - num;
        if (i < vec2.size())
            num -= vec2[i];
        if (num >= 0)
            re.push_back (num), num = 0;
        else
            re.push_back (mod + num), num = 1;
    }
    for (int i = re.size() - 1; i >= 0; i--) {
        if (re[i] == 0)
            sum++;
        else
            break;
    }
    re.resize (re.size() - sum);
    if (re.size() == 0)
        re.push_back (0);
    return re;
}
vector<int>mult (vector<int>vec1, vector<int>vec2) {
    vector<int>re;
    if ( (vec1.size() == 1 && vec1[0] == 0) || (vec2.size() == 1 && vec2[0] == 0)) {
        re.push_back (0);
        return re;
    }
    long long num = 0;
    for (int i = 0; i < vec1.size(); i++)
        for (int j = 0; j < vec2.size(); j++) {
            num += (long long) vec1[i] * vec2[j];
            if (i + j >= re.size())
                re.push_back (0);
            num += re[i + j];
            re[i + j] = num % mod;
            num /= mod;
        }
    while (num)
        re.push_back (num % mod), num /= mod;
    return re;
}
vector<int>Int_To_Vec (int n) {
    vector<int>re;
    re.push_back (n);
    return re;
}
int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    string str;
    while (cin >> str) {
        vector<int>vec, left;
        int now = 0, pos = 0;
        bool point = 0;
        if (str.length() % 2 == 1)
            pos = 1, vec.push_back (str[0] - '0');
        else
            pos = 2, vec.push_back ( (str[0] - '0') * 10 + str[1] - '0');
        left.push_back (0);
        while (1) {
            left = mult (plu (left, Int_To_Vec (left[0] % 10)), Int_To_Vec (10));
            if (point == 0) {
                for (int i = 1; i <= 9; i++) {
                    if (bigger (mult (plu (left, Int_To_Vec (i)), Int_To_Vec (i)), vec) == 1) {
                        cout << i - 1;
                        left = plu (left, Int_To_Vec (i - 1));
                        vec = dec (vec, mult (left, Int_To_Vec (i - 1)));
                        break;
                    }
                    if (i == 9) {
                        cout << '9';
                        left = plu (left, Int_To_Vec (9));
                        vec = dec (vec, mult (left, Int_To_Vec (9)));
                    }
                }
                if (pos == str.length()) {
                    cout << '.';
                    point = 1;
                    continue;
                }
                vec = plu (mult (vec, Int_To_Vec (100)), Int_To_Vec (10 * (str[pos] - '0') + str[pos + 1] - '0'));
                pos += 2;
            } else {
                vec = mult (vec, Int_To_Vec (100));
                for (int i = 1; i <= 9; i++) {
                    if (bigger (mult (plu (left, Int_To_Vec (i)), Int_To_Vec (i)), vec) == 1) {
                        cout << i - 1;
                        left = plu (left, Int_To_Vec (i - 1));
                        vec = dec (vec, mult (left, Int_To_Vec (i - 1)));
                        break;
                    }
                    if (i == 9) {
                        cout << '9';
                        left = plu (left, Int_To_Vec (9));
                        vec = dec (vec, mult (left, Int_To_Vec (9)));
                    }
                }
                now++;
                if (now == 50)
                    break;
            }
        }
        cout << '\n';
    }
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！