大数除法

tip

大数除法是指被除数大小超出long long范围，而导致必须使用字符串存储的除法，属于简单模拟的范畴

思路

通过模拟列竖式手动计算除法，实现使用字符串存储被除数的大数除法

参考代码

string division(string s, int divisor) {
    /*
     * 通过模拟列竖式手算除法完成字符串存储的大数除法
     */
    string quotient; // 商
    int idx = 0; // 当前处理的数字在原始字符串中的位置
    int remainder = 0; // 余数
    int temp = 0;
    while (idx < s.size()) { // 一直循环处理到索引等于长度
        temp = remainder * 10 + (s[idx] - '0'); // 当前进行除法运算的temp
        if (temp >= divisor) { // 如果能除的动，则将当前的商插入quotient，并更新余数
            quotient.push_back(temp / divisor + '0');
            remainder = temp % divisor;
        } else { // 除不动时分两种情况
            if (!quotient.empty()) { // 商目前不为空，此时按照竖式方法，需要向商中加入0，再接着下一次循环
                quotient.push_back('0');
            }
            remainder = temp; // 商目前为空，按照竖式计算方法，只更新余数，商保持为空
        }
        idx++; // 更新索引位置
    }
    if (quotient.empty()) { // 如果一直除不动，循环结束商还为空，则赋值为0字符串
        quotient.assign("0");
    }
    return quotient; // 返回商字符串
}

扩展

将大数除法与进制转换相结合。

tip

北京大学机试真题，N诺链接

完整代码如下：

#include <bits/stdc++.h>

using namespace std;

string division(string s, int divisor) {
    /*
     * 通过模拟列竖式手算除法完成字符串存储的大数除法
     */
    string quotient; // 商
    int idx = 0; // 当前处理的数字在原始字符串中的位置
    int remainder = 0; // 余数
    int temp = 0;
    while (idx < s.size()) { // 一直循环处理到索引等于长度
        temp = remainder * 10 + (s[idx] - '0'); // 当前进行除法运算的temp
        if (temp >= divisor) { // 如果能除的动，则将当前的商插入quotient，并更新余数
            quotient.push_back(temp / divisor + '0');
            remainder = temp % divisor;
        } else { // 除不动时分两种情况
            if (!quotient.empty()) { // 商目前不为空，此时按照竖式方法，需要向商中加入0，再接着下一次循环
                quotient.push_back('0');
            }
            remainder = temp; // 商目前为空，按照竖式计算方法，只更新余数，商保持为空
        }
        idx++; // 更新索引位置
    }
    if (quotient.empty()) { // 如果一直除不动，循环结束商还为空，则赋值为0字符串
        quotient.assign("0");
    }
    return quotient; // 返回商字符串
}

int main() {
    string s;
    while (cin >> s) {
        vector<int> vec;
        int len = s.size();
        while (s != "0") {
            int remainder = (s[len - 1] - '0') % 2;
            vec.push_back(remainder);
            s = division(s, 2);
            len = s.size();
        }
        if (vec.empty()) {
            cout << "0";
        } else {
            for (auto it = vec.rbegin(); it != vec.rend(); it++) {
                cout << *it;
            }
        }
        cout << endl;
    }
    return 0;
}