高精度算法
2026-06-13 13:57:56
发布于：广东
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
输出：
1
四、高精度乘法
思路：用双重循环模拟竖式乘法，位置 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
输出：
7006652
五、高精度除法（高精度 ÷ 低精度）
思路：从高位到低位逐位处理，每次用当前余数×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加下一位再除 |
| 除法（÷高精度） | 用减法模拟 | 每次减去除数的倍数 |
八、记忆口诀
高精度，数组存，倒序存储个位低
加法进位往前加，减法借位要仔细
乘法双重循环算，最后统一处理进
除法高位逐位除，余数乘十加下位
全部评论 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牛逼!!!!
2天前 来自 广东
1
有帮助，赞一个