Skip to content

11026: 【原1026】高精度除法

题目

题目描述

author: 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1026

Description

给定两个整数A和B，求A/B。

Input Format

第一行：A

第二行：B

保证A和B的位数少于或等于10000。

Output Format

一行，A/B

Sample Input

10
5

Sample Output

2

FineArtz's solution 

/* 高精度除法 */
#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

const int MAXS = 10005;

int sub(int a[], int b[], int lena, int lenb, int shift = 0){
    if (lena < lenb + shift) return -1;
    if (lena == lenb + shift){
        for (int i = lenb; i >= 1; --i){
            if (a[i + shift] > b[i]) break;
            if (a[i + shift] < b[i]) return -1;
        }
    }
    for (int i = shift + 1; i <= lena; ++i){
        a[i] -= b[i - shift];
        if (a[i] < 0){
            a[i] += 10;
            --a[i + 1];
        }
    }
    for (int i = lena; i != 0; --i){
        if (a[i]) return i;
    }
    return 0;
}

int a[MAXS] = {0}, b[MAXS] = {0}, ans[MAXS] = {0};

int main(){
    string s1, s2;
    bool flag = 1;
    getline(cin ,s1);
    getline(cin, s2);
    while (s1.size() != 0 && s1[0] == '0') s1.erase(s1.begin());
    while (s2.size() != 0 && s2[0] == '0') s2.erase(s2.begin());
    int lena = s1.size(), lenb = s2.size();
    if (lena == 0){
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= lena; ++i)
        a[i] = s1[lena - i] - '0';
    for (int i = 1; i <= lenb; ++i)
        b[i] = s2[lenb - i] - '0';
    if (lena < lenb){
        printf("0\n");
        return 0;
    }
    int def = lena - lenb;
    int sublen = 0;
    for (int i = def; i >= 0; --i){
        while ((sublen = sub(a, b, lena, lenb, i)) >= 0){
            lena = sublen;
            ++ans[i + 1];
        }
    }
    int len = def + 1;
    while (len >= 1 && ans[len] == 0) --len;
    if (len > 0){
        for (int i = len; i != 0; --i) printf("%d", ans[i]);
    }
    else printf("0");
    return 0;
}

ligongzzz's solution 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;


//定义一个数类，可接收普通整数、大整数、小数等等作为实例
class Number
{
    //请在此添加‘Number’类的实现代码
    /********** Begin **********/
public:
    vector<int> lnum, rnum;
    //判断是否正常
    bool status = true, is_rnum = false, op = true;

    Number(const Number& other) :lnum(other.lnum), rnum(other.rnum),
        status(other.status), is_rnum(other.is_rnum), op(other.op) {}
    Number(const string& str) {
        int cnt = 0;
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            if (str[i] == '-') {
                if (i == 0) {
                    op = false;
                }
                else {
                    status = false;
                    break;
                }
            }
            else if (str[i] == '.') {
                is_rnum = true;
                ++cnt;
            }
            else {
                if (!(str[i] >= '0' && str[i] <= '9')) {
                    status = false;
                    break;
                }
                if (cnt == 0) {
                    lnum.emplace_back(str[i] - '0');
                }
                else if (cnt == 1) {
                    rnum.emplace_back(str[i] - '0');
                }
                else {
                    status = false;
                    break;
                }
            }
        }
    }
    Number(bool op, const vector<int> num_list, int ppos) :op(op) {
        if (ppos <= num_list.size())
            lnum.assign(num_list.begin(), num_list.end() - ppos);
        if (ppos) {
            if (ppos > num_list.size()) {
                rnum = vector<int>(ppos - num_list.size(), 0);
                for (auto p : num_list)
                    rnum.emplace_back(p);
            }
            else
                rnum.assign(num_list.end() - ppos, num_list.end());
            is_rnum = true;
        }
    }

    bool check() {
        if (is_rnum && lnum.size() + rnum.size() + 1 > 128) {
            status = false;
        }
        else if (!is_rnum && lnum.size() > 128) {
            status = false;
        }

        return status;
    }

    void cut() {
        if (is_rnum > 0) {
            int cut_num = int(!op) + lnum.size() + rnum.size() + 1 - 128;
            if (rnum.size() >= cut_num) {
                rnum.erase(rnum.end() - cut_num, rnum.end());
            }
        }
    }

    void print() {
        if (!op)
            cout << "-";
        for (auto p : lnum)
            cout << p;
    }
    /********** End **********/
};


//定义一个表达式类，支持任意两个Number类实例的加减乘除操作，计算规则满足一般的数学计算法则
class Expression
{
    //请在此添加‘Expression’类的实现代码
    /********** Begin **********/
    //简化运算结果
    void simplify(Number& num) const {
        int length = num.lnum.size(), pos = 0;
        for (; pos < length - 1; ++pos) {
            if (num.lnum[pos] != 0)
                break;
        }
        if (pos != 0)
            num.lnum.assign(num.lnum.begin() + pos, num.lnum.end());

        if (num.is_rnum) {
            for (pos = num.rnum.size() - 1; pos >= 0; --pos) {
                if (num.rnum[pos] == 0)
                    num.rnum.pop_back();
                else
                    break;
            }
            if (pos < 0)
                num.is_rnum = false;
        }
        if (num.lnum.empty())
            num.lnum.emplace_back(0);
        if (!num.is_rnum && num.lnum.size() == 1 && num.lnum[0] == 0)
            num.op = true;
    }
    void simplify(vector<int>& num) const {
        int length = num.size(), pos = 0;
        for (; pos < length; ++pos) {
            if (num[pos] != 0)
                break;
        }
        if (pos != length) {
            num.assign(num.begin() + pos, num.end());
        }
        else {
            num = vector<int>(1, 0);
        }
    }
    //转为运算模式数
    int change(const Number& a, const Number& b, vector<int>& an, vector<int>& bn) const {
        int ppos = 0;
        for (auto p : a.lnum)
            an.emplace_back(p);
        for (auto p : b.lnum)
            bn.emplace_back(p);
        //扩充为小数
        if (a.is_rnum || b.is_rnum) {
            ppos = max(a.rnum.size(), b.rnum.size());

            for (int i = 0; i < ppos; ++i) {
                an.emplace_back(i < a.rnum.size() ? a.rnum[i] : 0);
                bn.emplace_back(i < b.rnum.size() ? b.rnum[i] : 0);
            }
        }
        return ppos;
    }
    //比较数字大小
    int compare(const vector<int>& an, const vector<int>& bn) const {
        if (an.size() < bn.size()) {
            return -1;
        }
        else if (an.size() > bn.size()) {
            return 1;
        }
        else {
            int length = an.size();
            for (int i = 0; i < length; ++i) {
                if (an[i] < bn[i])
                    return -1;
                if (an[i] > bn[i])
                    return 1;
            }
            return 0;
        }
    }
public:
    //对正整数的四则运算
    vector<int> add_raw(const vector<int>& an, const vector<int>& bn) const {
        vector<int> ans;
        int jw = 0;
        for (int i = an.size() - 1, j = bn.size() - 1; jw || i >= 0 || j >= 0;) {
            int x, y;
            if (i >= 0) {
                x = an[i];
                --i;
            }
            else
                x = 0;
            if (j >= 0) {
                y = bn[j];
                --j;
            }
            else
                y = 0;
            if (x + y + jw >= 10) {
                ans.emplace_back(x + y + jw - 10);
                jw = 1;
            }
            else {
                ans.emplace_back(x + y + jw);
                jw = 0;
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

    vector<int> minus_raw(const vector<int>& an, const vector<int>& bn) const {
        vector<int> ans;
        int jw = 0;
        for (int i = an.size() - 1, j = bn.size() - 1; jw || i >= 0 || j >= 0;) {
            int x, y;
            if (i >= 0) {
                x = an[i];
                --i;
            }
            else
                x = 0;
            if (j >= 0) {
                y = bn[j];
                --j;
            }
            else
                y = 0;
            if (x - y - jw < 0) {
                ans.emplace_back(x - y - jw + 10);
                jw = 1;
            }
            else {
                ans.emplace_back(x - y - jw);
                jw = 0;
            }
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }

    vector<int> times_raw(const vector<int>& an, const vector<int>& bn) const {
        int al = an.size(), bl = bn.size();

        vector<int> ans(1, 0);
        for (int i = bl - 1; i >= 0; --i) {
            vector<int> temp;
            int jw = 0;
            for (int j = al - 1; j >= 0; --j) {
                temp.emplace_back((jw + an[j] * bn[i]) % 10);
                jw = (jw + an[j] * bn[i]) / 10;
            }
            if (jw)
                temp.emplace_back(jw);
            reverse(temp.begin(), temp.end());
            for (int k = 0; k < bl - i - 1; ++k)
                temp.emplace_back(0);
            ans = add_raw(ans, temp);
        }

        return ans;
    }

    int devides_raw(const vector<int>& an_raw, const vector<int>& bn, vector<int>& ans) const {
        int ppos = 0;
        vector<int> an(an_raw);
        int al = an.size(), bl = bn.size();

        //补齐
        for (; al < bl; ++al) {
            an.emplace_back(0);
            ++ppos;
        }

        //计算9个bl的乘积值
        vector<vector<int>> fast_ans(10);
        fast_ans[0] = vector<int>(1, 0);
        for (int i = 1; i < 10; ++i) {
            fast_ans[i] = add_raw(fast_ans[i - 1], bn);
        }

        vector<int> temp(an.begin(), an.begin() + bl);
        for (int pos = 0;; ++pos) {
            for (int i = 9; i >= 0; --i) {
                if (compare(temp, fast_ans[i]) >= 0) {
                    ans.emplace_back(i);
                    temp = minus_raw(temp, fast_ans[i]);
                    break;
                }
            }
            simplify(temp);
            if (temp.size() == 1 && temp[0] == 0 && pos + bl >= al) {
                break;
            }
            if (ppos >= 2)
                break;
            //移动到下一位
            if (pos + bl + 1 <= al) {
                temp.emplace_back(an[pos + bl]);
            }
            else {
                ++ppos;
                temp.emplace_back(0);
            }
            simplify(temp);
        }

        return ppos;
    }

    Number add(const Number& a, const Number& b) {
        vector<int> an, bn;
        int ppos = change(a, b, an, bn);

        if (a.op && b.op) {
            vector<int> ans = add_raw(an, bn);
            Number ans_num(true, ans, ppos);
            simplify(ans_num);
            return ans_num;
        }
        else if (a.op && !b.op) {
            if (compare(an, bn) >= 0) {
                vector<int> ans = minus_raw(an, bn);
                Number ans_num(true, ans, ppos);
                simplify(ans_num);
                return ans_num;
            }
            else {
                vector<int> ans = minus_raw(bn, an);
                Number ans_num(false, ans, ppos);
                simplify(ans_num);
                return ans_num;
            }
        }
        else if (!a.op && b.op) {
            if (compare(an, bn) >= 0) {
                vector<int> ans = minus_raw(an, bn);
                Number ans_num(false, ans, ppos);
                simplify(ans_num);
                return ans_num;
            }
            else {
                vector<int> ans = minus_raw(bn, an);
                Number ans_num(true, ans, ppos);
                simplify(ans_num);
                return ans_num;
            }
        }
        else {
            vector<int> ans = add_raw(an, bn);
            Number ans_num(false, ans, ppos);
            simplify(ans_num);
            return ans_num;
        }
    }

    Number minus(const Number& a, const Number& b) {
        Number nb(b);
        nb.op = !nb.op;

        return add(a, nb);
    }

    Number times(const Number& a, const Number& b) {
        vector<int> an, bn;
        int ppos = 2 * change(a, b, an, bn);

        if (a.op == b.op) {
            vector<int> ans = times_raw(an, bn);
            Number ans_num(true, ans, ppos);
            simplify(ans_num);
            return ans_num;
        }
        else {
            vector<int> ans = times_raw(an, bn);
            Number ans_num(false, ans, ppos);
            simplify(ans_num);
            return ans_num;
        }
    }

    Number devides(const Number& a, const Number& b) {
        vector<int> an, bn, ans;
        change(a, b, an, bn);
        simplify(an);
        simplify(bn);

        int ppos = devides_raw(an, bn, ans);
        if (bn.size() == 1 && bn[0] == 0) {
            Number ans_num(true, ans, ppos);
            ans_num.status = false;
            return ans_num;
        }
        if (a.op == b.op) {
            Number ans_num(true, ans, ppos);
            simplify(ans_num);
            ans_num.cut();
            return ans_num;
        }
        else {
            Number ans_num(false, ans, ppos);
            simplify(ans_num);
            ans_num.cut();
            return ans_num;
        }
    }
    /********** End **********/
};


//定义main函数
int main()
{
    /********** Begin **********/
    Expression expression;

    string a, b;
    cin >> a >> b;

    expression.devides(a, b).print();

    //请打印输出运算结果，输出结果时无需换行


    /********** End **********/
    return 0;
}