数字计数题两种解法对比

暴力极致常数优化 + 数学推导O(logN)通杀大数据

本题解制作不易，可以点点赞吗？Thanks♪(･ω･)ﾉ

一、题目简述

题意

给定 $M,N$，统计区间 $[M,N]$ 内数字0~9各自出现次数。

数据范围

$1\le M\le N\le 2\times 10^9$，$N-M\le 5\times 10^5$

样例

输入：129 137
输出：1 10 2 9 1 1 1 1 0 1

二、题意分析数据范围关键点

1. 区间长度最大 $5\times 10^5$：暴力拆解每位数字可过，只需极致常数优化；
2. 若题目取消区间限制、仅给 $1\le M\le N\le 10^{18}$，暴力必TLE，必须数位统计；
3. 原暴力代码存在两个致命问题：
   • while(x) 无法统计数字0；
   • cin/cout IO过慢，大数据容易TLE；
   • 循环变量int存不下大数，存在溢出风险。

三、方案1：原题暴力极致常数优化（不改核心遍历逻辑）

完全保留「遍历每个数→逐位拆分统计」原始逻辑，仅做IO、循环、分支常数优化，适配本题给定区间限制。

#define ll long long
#include<cstdio>
int main(){
    ll l,r,vis[10]={0};
    scanf("%lld%lld",&l,&r);
    for(ll i=l;i<=r;++i){
        ll x=i;
        do{
            vis[x%10]++;
            x/=10;
        }while(x);
    }
    for(int i=0;i<10;++i)printf("%lld ",vis[i]);
    return 0;
}

优化点说明（完全不改动统计逻辑）

1. 移除万能头，仅引入<cstdio>，减少程序加载内存，规避glibc额外开销；
2. cin/cout 替换为scanf/printf，关闭同步开销，IO速度提升数倍；
3. while(x) 改为do-while：天然兼容数字0，省去单独判断if(!x)分支，减少判断耗时；
4. 循环变量统一ll，避免大数区间溢出；
5. 无全局数组，vis存栈，内存占用恒定极小，不会MLE；
6. 前置++i替代后置i++，减少临时变量拷贝常数开销。

适用场景

本题限定 $N-M\le 5\times 10^5$，此代码速度足够，代码简短易写，适合赛时快速敲出。

四、方案2：数学推导通用解法（通杀所有超大区间）

数位计数数学完整推导（求 $1\sim X$ 数码 $d$ 出现次数）

设数字按位拆分：

$$X = \overline{high\ cur\ low}$$

• $p=10^k$：当前位权（第 $k$ 位）
• $cur = \left\lfloor \frac{X}{p} \right\rfloor \bmod 10$：当前位数字
• $high = \left\lfloor \frac{X}{10p} \right\rfloor$：高位整体
• $low = X \bmod p$：低位整体

分两类：$d\neq 0$、$d=0$（0不能做前导，公式不同）

1、$d \neq 0$

1. $d < cur$
   高位可取 $0\sim high$，低位任意 $0\sim p-1$

$$ans += (high+1)\times p$$

2. $d = cur$
   高位 $0\sim high-1$ 完整一组 + 高位=$high$ 时低位 $0\sim low$

$$ans += high\times p + (low+1)$$

3. $d > cur$
   高位仅 $0\sim high-1$

$$ans += high\times p$$

2、$d = 0$（最高位不能为0，高位从 $1$ 开始）

1. $0 < cur$
   高位可取 $1\sim high$

$$ans += high\times p$$

2. $0 = cur$
   高位 $1\sim high-1$ 完整一组 + 高位=$high$ 低位 $0\sim low$

$$ans += (high-1)\times p + (low+1)$$

3. $0 > cur$ 不可能，无贡献

$$ans += (high-1)\times p$$

3、区间答案公式

$[L,R]$ 中数码 $d$ 出现次数：

$$f(R,d) - f(L-1,d)$$

$f(x,d)$ 代表 $1\sim x$ 数码 $d$ 总次数。

4、纯数学推导实现AC代码

#define ll long long
#include<cstdio>
ll get(ll x,int d){
    ll res=0,p=1;
    while(p<=x){
        ll cur=x/p%10;
        ll high=x/(p*10);
        ll low=x%p;
        if(d!=0){
            if(d<cur) res+=(high+1)*p;
            else if(d==cur) res+=high*p+low+1;
            else res+=high*p;
        }else{
            if(cur>0) res+=high*p;
            else res+=(high-1)*p+low+1;
        }
        p*=10;
    }
    return res;
}
int main(){
    ll L,R;
    scanf("%lld%lld",&L,&R);
    for(int d=0;d<=9;d++){
        ll ans=get(R,d)-get(L-1,d);
        printf("%lld ",ans);
    }
    return 0;
}

5、样例代入验算：输入 129 137

计算 $get(137,d)-get(128,d)$，输出严格匹配样例：
1 10 2 9 1 1 1 1 0 1

6、复杂度证明

每轮循环 $p$ 乘10，循环次数等于数字位数 $\log\\_{10}X$，单次循环固定10个数字遍历，总时间 $O(\log X)$；
仅常数变量，空间 $O(1)$，极致时空。

五、两种方案取舍实战建议

1. 赛时快速过题、题目限制区间长度：直接用优化暴力，代码短、思考成本低；
2. 题目无区间上限、$N-M$可达$10^{12}$：必须用数位统计，暴力直接TLE；
3. 内存严苛1MB限制场景：两种代码均无大数组、无STL容器，裸编译-nostdlib均可进一步压内存防MLE。

四、样例测试验证

输入：129 137
两段代码输出统一为：1 10 2 9 1 1 1 1 0 1，统计结果完全正确。

五、总结

1. 暴力优化版是针对本题数据范围的最优手写速敲代码，逻辑贴合初学者原始思路，仅做常数优化；
2. 数位统计是通用万能解法，复杂度碾压暴力，适合所有数位计数类拓展题；
3. 两种代码均无冗余代码、低内存占用，适配ACGO巅峰赛各类阴间内存、时间限制测试点。

六、方案2成果展示

这个方案时间$O(\log X)$,空间$O(1)$，达到完美代码
图片为证：

本蒟蒻也是通过这道题，获得了“时空双修”
(*^▽^*)