高精度运算

高精度运算主要解决的是在进行基本运算时输入或输出数据的大小超出了 long long的范围的问题，利用string对运算进行转换即可解决。

以下附上代码:

高精度加法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
string add(string a, string b) {
    string res = "";          // 用于存储结果（此时是逆序的）
    int i = a.size() - 1;     // a 的指针，从个位开始
    int j = b.size() - 1;     // b 的指针，从个位开始
    int carry = 0;            // 进位标记，初始为 0
    while (i >= 0 || j >= 0 || carry > 0) {
        // 1. 获取当前位的数字，如果指针越界则视为 0
        int digitA = (i >= 0) ? (a[i] - '0') : 0;
        int digitB = (j >= 0) ? (b[j] - '0') : 0;
        // 2. 计算当前位的总和（包含上一位的进位）
        int sum = digitA + digitB + carry;
        // 3. 更新进位：总和除以 10
        carry = sum / 10;
        // 4. 获取当前位保留的数字：总和模 10，并转为字符添加到结果末尾
        char currentChar = (sum % 10) + '0';
        res.push_back(currentChar);
        i--;
        j--;
    }
    // 因为是从个位开始添加的，所以结果现在是逆序的，需要反转
    reverse(res.begin(), res.end());
    return res.empty() ? "0" : res;
}

高精度减法(a>=b)

1
2
3
4
5
6
7
8
9
10
11
12
13
string sub(string a, string b) {
    string res;
    int i = a.size() - 1, j = b.size() - 1, borrow = 0;
    while(i >= 0) {
        int diff = (a[i--] - '0') - borrow - (j >= 0 ? b[j--] - '0' : 0);
        if(diff < 0) { diff += 10; borrow = 1; }
        else borrow = 0;
        res += diff+'0';
    }
    while(res.size() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res.empty() ? "0" : res;
}

高精度乘法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
string mul(string a, string b) {
    if(a == "0" || b == "0") return "0";
    vector<int> res(a.size() + b.size(), 0);
    // i 从 a 的最后一位（个位）向前遍历到第 0 位
    for(int i = a.size() - 1; i >= 0; i--)
        // j 从 b 的最后一位（个位）向前遍历到第 0 位
        for(int j = b.size() - 1; j >= 0; j--) 
            // 【计算当前位的乘积】
            // 将字符转换为整数进行相乘 (例如 '3'-'0' = 3)
            int prod = (a[i] - '0') * (b[j] - '0');
            // 【累加到对应位置】
            // 关键逻辑：a 的第 i 位 和 b 的第 j 位 相乘，结果应该累加到 res 的 i+j+1 位置
            // 这里 i+j+1 对应当前位的“本位”，i+j 对应“进位位”
            res[i + j + 1] += prod;
            // 【处理进位】
            res[i + j] += res[i + j + 1] / 10;
            res[i + j + 1] %= 10;
        }
    string ans;  
    // 【跳过前导零】
    int i = 0;
    while(i < res.size() && res[i] == 0) i++;
    for(; i < res.size(); i++) 
        ans += to_string(res[i]);
    return ans.empty() ? "0" : ans;
}

高精度除法(除以int)

1
2
3
4
5
6
7
8
9
10
11
12
13
string div(string a, int b) {
    string res;
    int remainder = 0;
    for(char c : a) {
        int cur = remainder * 10 + (c - '0');
        res += to_string(cur / b);
        remainder = cur % b;
    }
    int i = 0;
    while(i < res.size() && res[i] == '0') i++;
    res = res.substr(i);
    return res.empty() ? "0" : res;
}

高精度取模(除以int)

1
2
3
4
5
6
int mod(string a, int b) {
    int remainder = 0;
    for(char c : a)
        remainder = (remainder * 10 + (c - '0')) % b;
    return remainder;
}