【C++题解】P10840 星际能量分配：高精度除以低精度算法详解

好的，我们先来分析一下这道题。 ## 🧠 题目理解 - **N** 是一个最多 1000 位的超大整数（用字符串读入）。 - **K** 是一个普通整数（≤ 10⁷）。 - 要求计算 `N / K` 的整数商和余数。 - 输出商（无前导零）和余数各占一行。 由于 N 太大，无法直接用 `long long` 或 `int` 存储，必须用**高精度除法（大数除以普通整数）** 来模拟手算除法过程。 ## 📦 核心思路 模拟竖式除法： 1. 从 N 的最高位开始，逐位处理。 2. 当前余数 `remainder` 初始为 0。 3. 对于每一位数字 `digit`： - `current = remainder * 10 + digit` - 商的一位 = `current / K` - 新的余数 = `current % K` 4. 收集商的每一位，最后去掉可能的前导零（如果商是 0 则保留一位 0）。 ## 🛠️ C++ 实现代码 ```cpp #include <iostream> #include <string> #include <vector> using namespace std; int main() { string N; int K; cin >> N >> K; long long remainder = 0; // 余数，因为 K ≤ 10^7，所以余数不会超过 long long 范围 vector<int> quotient; // 存储商的每一位 // 逐位处理大数 N for (char ch : N) { int digit = ch - '0'; long long current = remainder * 10 + digit; quotient.push_back(current / K); remainder = current % K; } // 输出商（去掉前导零，但如果商是 0 则保留一位） int start = 0; while (start < quotient.size() && quotient[start] == 0) { start++; } if (start == quotient.size()) { // 说明商是 0 cout << 0 << endl; } else { for (int i = start; i < quotient.size(); i++) { cout << quotient[i]; } cout << endl; } // 输出余数 cout << remainder << endl; return 0; } ``` ## 📝 代码解释 1. **输入处理**：`N` 用 `string` 读入，`K` 用 `int` 读入。 2. **逐位除法**： - `remainder` 初始为 0。 - 对 `N` 的每一位，计算 `current = remainder * 10 + digit`。 - 当前位的商是 `current / K`，存入 `quotient` 向量。 - 更新余数 `remainder = current % K`。 3. **输出商**： - 因为是从最高位开始计算的，所以 `quotient` 中存储的也是从最高位到最低位的商。 - 需要跳过前导零，但如果整个商都是 0（例如 N < K），则输出一个 0。 4. **输出余数**：直接输出最后的 `remainder`。 ## ⚠️ 注意事项 - **余数范围**：由于 `K ≤ 10⁷`，且 `current = remainder * 10 + digit`，`remainder` 最大可能接近 `10⁷`，乘以 10 再加 9 仍在 `long long` 范围内（约 9e18），所以用 `long long` 存余数足够安全。 - **前导零处理**：商的输出不能有前导零，但若商为 0 应输出 `0`。 - **效率**：算法复杂度 O(n)，n 为 N 的位数（≤ 1000），完全可行。 ## 🚀 进阶与优化 - 如果 K 也很大（比如也是大数），则需要实现**高精度除以高精度**的算法，更复杂。 - 本题 K 较小，所以用普通整数运算即可。 - 可以边计算边输出商，避免存储 `quotient` 向量，但为了逻辑清晰，这里先存储再输出。 ## 📚 相关学习资源 - **高精度运算**：是算法竞赛基础内容，建议掌握加、减、乘（高精度×低精度、高精度×高精度）、除（高精度÷低精度、高精度÷高精度）。 - **推荐练习**：POJ 1001（高精度幂运算）、洛谷 P1601（A+B Problem，高精度加法）。 ## 💡 开发建议 1. **边界测试**：测试 N=“1”, K=1；N=“100”, K=99；N=“0”（但题目说无前导零，所以 N≥1）；N 位数很多且 K=1 或 K 很大等情况。 2. **代码可读性**：变量名尽量清晰，如 `remainder`、`quotient`。 3. **模块化**：如果项目中多处需要高精度运算，可封装成 `BigInteger` 类。 ######[AI写代码神器 | 1165点数解答 | 2026-04-10 21:10:07]