高精度算法

张kk

2026-06-13 13:57:56

发布于：广东

39阅读

0回复

0点赞

C++高精度算法笔记

一句话理解

高精度：用数组来存很大的整数（位数可达几千位），然后模拟竖式计算。

C++ 的 int 只能存约10位数，long long 也只能存约19位数。如果要计算 1000 位数字的加减乘除，就需要自己用数组来模拟。

一、高精度数的存储

常见方法：

用 string 读入
倒序存入 int 数组（个位放在 a[1]，十位放在 a[2]，这样方便进位）

string s;
cin >> s;
int a[10010] = {0};
int len = s.length();

// 倒序存储：a[1]存个位，a[2]存十位...
for (int i = 0; i < len; i++) {
    a[len - i] = s[i] - '0';
}

为什么要倒序？因为加法、乘法都可能进位，倒序后进位可以往后加，不需要移动整个数组。

二、高精度加法

思路：模拟竖式加法，从低位到高位逐位相加，处理进位。

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

int a[10010], b[10010], c[10010];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    // 倒序存入数组
    int len1 = s1.length(), len2 = s2.length();
    for (int i = 0; i < len1; i++) a[len1 - i] = s1[i] - '0';
    for (int i = 0; i < len2; i++) b[len2 - i] = s2[i] - '0';
    
    // 加法：逐位相加，处理进位
    int len = max(len1, len2);
    for (int i = 1; i <= len; i++) {
        c[i] = a[i] + b[i] + c[i];  // 加上下一位可能来的进位
        c[i + 1] = c[i] / 10;       // 进位
        c[i] %= 10;                  // 保留个位
    }
    
    // 输出：去掉前导零，倒序输出
    if (c[len + 1] > 0) len++;
    for (int i = len; i >= 1; i--) {
        cout << c[i];
    }
    cout << endl;
    
    return 0;
}

输入样例：

123456789
987654321

输出：

1111111110

三、高精度减法

思路：模拟竖式减法，从低位到高位逐位相减，不够就借位。

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

int a[10010], b[10010], c[10010];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    // 判断结果正负：如果 s1 < s2，则结果为负数，交换两个数
    bool negative = false;
    if (s1.length() < s2.length() || (s1.length() == s2.length() && s1 < s2)) {
        negative = true;
        swap(s1, s2);
    }
    
    int len1 = s1.length(), len2 = s2.length();
    for (int i = 0; i < len1; i++) a[len1 - i] = s1[i] - '0';
    for (int i = 0; i < len2; i++) b[len2 - i] = s2[i] - '0';
    
    // 减法：逐位相减，处理借位
    int len = max(len1, len2);
    for (int i = 1; i <= len; i++) {
        if (a[i] < b[i]) {
            a[i] += 10;      // 借位
            a[i + 1]--;
        }
        c[i] = a[i] - b[i];
    }
    
    // 去掉前导零
    while (len > 1 && c[len] == 0) len--;
    
    if (negative) cout << "-";
    for (int i = len; i >= 1; i--) {
        cout << c[i];
    }
    cout << endl;
    
    return 0;
}

输入样例：

1000
999

输出：

四、高精度乘法

思路：用双重循环模拟竖式乘法，位置 i 和位置 j 的乘积放在 c[i+j-1] 位置，最后统一处理进位。

原理：a[i] 表示 ×10^(i-1)，b[j] 表示 ×10^(j-1)，乘积就是 ×10^(i+j-2)，所以存在 c[i+j-1]。

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

int a[10010], b[10010], c[20010];

int main() {
    string s1, s2;
    cin >> s1 >> s2;
    
    int len1 = s1.length(), len2 = s2.length();
    for (int i = 0; i < len1; i++) a[len1 - i] = s1[i] - '0';
    for (int i = 0; i < len2; i++) b[len2 - i] = s2[i] - '0';
    
    // 乘法：双重循环
    for (int i = 1; i <= len1; i++) {
        for (int j = 1; j <= len2; j++) {
            c[i + j - 1] += a[i] * b[j];
        }
    }
    
    // 处理进位
    int len = len1 + len2;
    for (int i = 1; i <= len; i++) {
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    
    // 去掉前导零
    while (len > 1 && c[len] == 0) len--;
    
    for (int i = len; i >= 1; i--) {
        cout << c[i];
    }
    cout << endl;
    
    return 0;
}

输入样例：

1234
5678

输出：

五、高精度除法（高精度 ÷ 低精度）

思路：从高位到低位逐位处理，每次用当前余数×10加上下一位，再除以除数。

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

int a[10010], c[10010];

int main() {
    string s;
    int b;
    cin >> s >> b;
    
    int len = s.length();
    for (int i = 0; i < len; i++) {
        a[i + 1] = s[i] - '0';
    }
    
    // 除法：从高位到低位，正序处理
    long long remainder = 0;  // 余数
    for (int i = 1; i <= len; i++) {
        remainder = remainder * 10 + a[i];
        c[i] = remainder / b;
        remainder %= b;
    }
    
    // 去掉前导零
    int start = 1;
    while (start < len && c[start] == 0) start++;
    
    for (int i = start; i <= len; i++) {
        cout << c[i];
    }
    cout << endl;
    cout << "余数：" << remainder << endl;
    
    return 0;
}

输入样例：

123456789
13

输出：

9496676
余数：1

六、高精度除法（高精度 ÷ 高精度）

这个比较复杂，思路是模拟竖式除法：用减法来实现，每次减去除数的倍数。

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

string a, b;

// 比较两个高精度数的大小
bool cmp(string x, string y) {
    if (x.length() != y.length()) return x.length() > y.length();
    return x >= y;
}

// 高精度减法
string sub(string x, string y) {
    string res;
    int borrow = 0;
    int len1 = x.length(), len2 = y.length();
    
    // 倒序处理
    for (int i = 1; i <= len1; i++) {
        int xi = x[len1 - i] - '0';
        int yi = i <= len2 ? y[len2 - i] - '0' : 0;
        int diff = xi - yi - borrow;
        
        if (diff < 0) {
            diff += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        res += (diff + '0');
    }
    
    // 去除前导零
    while (res.length() > 1 && res.back() == '0') res.pop_back();
    reverse(res.begin(), res.end());
    return res;
}

// 高精度除法
string div(string a, string b) {
    string res, remainder;
    int len = a.length();
    
    for (int i = 0; i < len; i++) {
        remainder += a[i];  // 取一位下来
        
        // 去掉 remainder 的前导零
        int pos = 0;
        while (pos < remainder.length() - 1 && remainder[pos] == '0') pos++;
        remainder = remainder.substr(pos);
        
        // 计算当前位商几
        int count = 0;
        while (cmp(remainder, b)) {
            remainder = sub(remainder, b);
            count++;
        }
        res += (count + '0');
    }
    
    // 去掉前导零
    int pos = 0;
    while (pos < res.length() - 1 && res[pos] == '0') pos++;
    res = res.substr(pos);
    
    return res;
}

int main() {
    cin >> a >> b;
    
    if (b == "0") {
        cout << "除数不能为0" << endl;
        return 0;
    }
    
    if (!cmp(a, b)) {
        cout << "0" << endl;
        return 0;
    }
    
    string ans = div(a, b);
    cout << ans << endl;
    
    return 0;
}

七、四种运算总结

运算	方向	核心要点
加法	从低位到高位	逐位相加，处理进位
减法	从低位到高位	逐位相减，处理借位，判断负数
乘法	双重循环	`c[i+j-1] += a[i] * b[j]`，最后进位
除法（÷低精度）	从高位到低位	每次用当前余数×10加下一位再除
除法（÷高精度）	用减法模拟	每次减去除数的倍数

八、记忆口诀

高精度，数组存，倒序存储个位低
加法进位往前加，减法借位要仔细
乘法双重循环算，最后统一处理进
除法高位逐位除，余数乘十加下位

有帮助，赞一个

去预览

0/2000

全部评论 1

立春男明星(关必回）
张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!张kk牛逼!!!!

2026-06-13 来自广东
1