高效统计数字1出现次数：C++数位DP解法详解

这是一个经典的数位DP（Digit DP）问题，或者可以采用暴力枚举解法（当 n 较小时）。这里给出更高效的数位DP解法，时间复杂度 O(log₁₀(n))。 ## 🔍 问题分析 统计从 1 到 n 的所有数字中，数字 1 在每一位上出现的总次数。例如 n=12，个位上 1 出现 2 次（1 和 11），十位上 1 出现 3 次（10、11、12），总计 5 次。 ## 🧮 高效解法（逐位计算） 对每一位，计算该位出现 1 的次数，然后累加。核心公式基于当前位的数字分为三种情况（小于1、等于1、大于1）。 ### 💻 C++ 代码实现 ```cpp #include <iostream> using namespace std; long long countDigitOne(long long n) { long long count = 0; long long factor = 1; // 表示当前位，1表示个位，10表示十位... while (factor <= n) { long long lower = n % factor; // 低位数字 long long current = (n / factor) % 10; // 当前位数字 long long higher = n / (factor * 10); // 高位数字 if (current == 0) { count += higher * factor; } else if (current == 1) { count += higher * factor + lower + 1; } else { // current > 1 count += (higher + 1) * factor; } factor *= 10; } return count; } int main() { long long n; cin >> n; cout << countDigitOne(n) << endl; return 0; } ``` ### 📖 代码原理解析 对每一位（个位、十位、百位...）分别计算数字 1 出现的次数： - **current = 0**：该位为 0 时，1 只出现在更高位变化中，次数为 `higher * factor`。 - **current = 1**：该位为 1 时，除了 `higher * factor` 次，还要加上低位从 0 到 lower 的所有情况，即 `lower + 1`。 - **current > 1**：该位大于 1 时，该位为 1 的次数为 `(higher + 1) * factor`。 ### 🧪 测试样例 | 输入 n | 输出 | 解释 | |--------|------|------| | 2 | 1 | 只有数字 1 含 1 | | 12 | 5 | 1, 10, 11, 12 中出现 5 个 1 | | 99 | 20 | 个位 10 次 + 十位 10 次 | ### ⚠️ 注意要点 - 使用 `long long` 类型防止 n 较大时溢出（如 n=10^9 时结果可能超过 int 范围）。 - 算法复杂度 O(log₁₀(n))，适合 n 极大（如 10^18）的情况。 ######[AI问答 | 727点数解答 | 2026-08-20 22:03:48]