NZOI练习题：高效统计0到N数字中3出现次数的算法优化方案咨询

嘿，你的暴力遍历解法逻辑完全没问题——逐个检查每个数的每一位是否为3，思路直接易懂，但正如你发现的，当N非常大（比如1e18这种量级）时，暴力遍历的时间复杂度是O(N * 位数)，肯定会超时。这里给你推荐逐位统计法，时间复杂度只和N的位数有关，不管N多大都能快速出结果。

核心思路 #

我们不用遍历每个数，而是逐位计算每一位上数字3出现的总次数，最后把所有位的结果加起来就行。举个具体的，比如看数字的第k位（从右往左数，从0开始算，个位是第0位），我们把整个数字拆成三个部分：

• 高位（higher）：第k位左边的所有数字
• 当前位（current）：第k位本身的数字
• 低位（lower）：第k位右边的所有数字
• 位权（power）：10^k，比如第0位是1，第1位是10，第2位是100，以此类推

然后分三种情况计算当前位上3出现的次数：

1. 如果当前位数字 小于3：当前位能出现3的次数就是 higher * power——因为高位可以从0到higher-1，每一种情况低位都可以从0到power-1，总共higher*power次
2. 如果当前位数字 等于3：次数是 higher * power + lower + 1——除了高位从0到higher-1的情况，当高位等于higher时，低位可以从0到lower，总共lower+1次
3. 如果当前位数字 大于3：次数是 (higher + 1) * power——高位可以从0到higher，每一种情况低位都可以从0到power-1，总共(higher+1)*power次

C++代码实现 #

#include <iostream>
using namespace std;

long long countThree(long long n) {
    long long count = 0;
    long long power = 1; // 从个位开始遍历每一位
    while (power <= n) {
        long long higher = n / (power * 10);
        long long current = (n / power) % 10;
        long long lower = n % power;
        
        if (current < 3) {
            count += higher * power;
        } else if (current == 3) {
            count += higher * power + lower + 1;
        } else {
            count += (higher + 1) * power;
        }
        power *= 10;
    }
    return count;
}

int main() {
    long long l;
    cin >> l;
    cout << countThree(l) << endl;
    return 0;
}

例子验证 #

拿你提到的N=13来测试：

• 个位（power=1）：higher=1，current=3，lower=0 → 次数是1*1 + 0+1=2
• 十位（power=10）：higher=0，current=1 <3 → 次数是0*10=0
• 总和是2+0=2，和例子结果完全一致。

再试个N=33：

• 个位：higher=3，current=3，lower=0 → 3*1 +0+1=4
• 十位：higher=0，current=3，lower=3 →0*10 +3+1=4
• 总和是8，对应数字3、13、23、30、31、32、33（33包含两个3），总共8次，完全正确。

这个算法不管N是1e18还是更大的数，都只需要循环N的位数次（最多18次），效率拉满～

内容的提问来源于stack exchange，提问作者Supesu