P1980计数问题，是NOIP 2013普及组的第一题。不少老选手把它当成梯队入门题，新手刚学会循环和取模就能做，但它实际上是个非常典型的数字统计题：给定n和x，要你数出1到n这n个整数里，数字x一共出现了多少次。题面看着简单，背后却藏着“按位贡献”这种在后来的提高组题目里反复出现的思想。这篇文章想以一种选手复盘的方式，从暴力模拟一路聊到按位计数法，再把x=0这个很多人翻车的边界摊开讲清楚。不管你是刚刷洛谷的新手，还是想补一补数字统计题底层的同学，应该都能有点收获。

1. 先聊聊这道普及组第一题到底考什么

1.1 从题目描述到真正的考点

原题给的数据范围是 1 ≤ n ≤ 1,000,000，0 ≤ x ≤ 9。输入两个整数，输出答案。比如 n=11、x=1，那么从1到11这些数字里，1出现了4次：1里面有一个1，10里面有一个1，11里面有两个1。这就是“计数问题”这个题名的由来：不是问你包含x的数有几个，而是问你x这个数字在所有数的十进制表示里一共出现了多少次。

很多新手拿到题目后的第一反应就是“那我挨个数”。这当然没错，因为这题 n 只有一百万，暴力拆数字完全来得及。但如果只停留在“会写循环”这个层面，就浪费了这道题真正的教学价值。它真正想考察的是两个基本功：第一，整数拆位的熟练度；第二，能不能从“一个数字一个数字看”升级到“每一位对答案的贡献独立计算”。后者这种思想，在后面的许多题目里都会有影子。

1.2 为什么一道“送分题”也值得较真

NOIP普及组第一题通常被称为“签到题”，但签到题不等于没营养。恰恰因为题目简单，数据范围刻意放得很宽，你才可以把精力集中在算法思维上，而不是去处理各种复杂数据结构。

我见过不少选手，靠暴力模板硬过了P1980，然后在做提高组或者更高级别的数字统计题时，发现暴力跑不动了，才回头补按位计数的知识。与其那样，不如一开始就把这道题吃透。而且这道题有一个特别容易踩的坑：x=0时，暴力法很容易算错或统计出前导零，按位计数法也要单独处理。这个坑在后来很多类似题目里都会换着法子出现，比如区间数字统计、数位DP的入门题，都是从这里长出来的。

2. 暴力模拟：把每个数字拆开数一遍，先跑通再说

2.1 数字拆分的基本操作

暴力法的思路非常直白：从1循环到n，对每个整数不断模10、除以10，把每一位拿出来和x比较，相等就计数。这里有一个初学者常纠结的细节：0怎么处理？

比如统计 x=0 时，如果当前数字就是0，那按“拆位统计”的逻辑，0的十进制表示是“0”，应该算有一个0。但这道题是从1开始的，所以不会出现单独的数0，不用担心。可是如果你以后写一个通用的 solve(0) 函数，就需要注意这个边界。我一般会写成：

• 如果数字是0，单独判断：如果统计0且区间包含0，则加1。
• 否则就 while (tmp > 0) 拆位。

对于P1980，因为从1开始，直接 while 循环就行。

拆位代码示意如下：

int countInNumber(int num, int x) { int cnt = 0; if (num == 0) { return x == 0 ? 1 : 0; } while (num > 0) { if (num % 10 == x) cnt++; num /= 10; } return cnt; }

然后主函数里从1加到n，累加所有 countInNumber 的结果。这个过程理解起来毫无压力，也很容易验证正确性。

2.2 暴力法的时间复杂度与评测环境

n 最大是一百万，每个数字最多7位，所以拆位次数最多约700万次，这个量级在一秒内跑完没有任何问题。哪怕你用 Python，一百万次循环加内层拆位，通常也能在1秒到2秒之间跑完，如果用的是 PyPy 更快。所以从“能不能过”的角度看，暴力解在P1980这道题里是完全合格的。

但这道题的数据范围再往上提到10^9、10^18，暴力就立刻原形毕露。你可以把暴力法当成验证工具，用来测试按位计数法的正确性：跑一个随机的小n，比较两种方法输出是否一致。这个方法我在调试时用了很多次，比自己空想要靠谱得多。

暴力法唯一要注意的是别写得太丑。有些人喜欢把数字转成字符串再数，那更慢也更麻烦，但也不是不能用。只是既然拆位是基础功，还是建议直接用取模实现，毕竟很多后续题目的状态转移都是基于拆位逻辑的。

3. 按位计数法：从“数数字”升级到“算贡献”

3.1 核心思想：去掉循环，改为逐位统计

如果说暴力法是从数字的视角看问题，那么按位计数法就是从“位”的视角看问题。对于一个数n，我们不去枚举1到n，而是分别去看个位、十位、百位……上x出现了多少次，再把所有位上的次数加起来。

举个例子：n=11，x=1。个位上，1出现几次？1和11都贡献了一个个位1，所以是2次。十位上，1出现几次？10和11的十位都是1，所以也是2次。总计4次。注意这里并没有去枚举所有数字，而是把所有数字按位切分后，统计每一位的贡献。

这种思路的数学基础是“贡献独立”：一个数字等于各个数位上数字的加权和，那么统计所有数字中x的出现次数，就等于统计所有数位上x的出现次数之和。听起来像废话，但它能把问题的复杂度从 O(n·位数) 降到 O(位数)。

3.2 三种情况的分类讨论

假设我们从低到高处理第 i 位，位权为 factor = 10^i。把n拆成三部分：

• high：当前位左边的高位部分，值为 n / (factor * 10)
• cur：当前位的数字，值为 (n / factor) % 10
• low：当前位右边的低位部分，值为 n % factor

比如 n=12345，处理十位时，factor=10，high=123，cur=4，low=5。

对于 x > 0 的情况，分类很清爽：

• 如果 cur < x：那么当前位上出现x的数有 high * factor 个。因为高位可以从0到high-1，低位可以从0到factor-1，排列组合一下就是 high * factor。
• 如果 cur == x：当前位上出现x的数有 high * factor + low + 1 个。前一部分和高位组合，后一部分是高位恰好等于high时，低位可以取0到low，共 low+1 个。
• 如果 cur > x：当前位上出现x的数有 (high + 1) * factor 个。因为高位等于high时，低位可以取0到factor-1，也合法。

这个公式不需要硬背，画一条数轴就能推出来。你只要理解“当前位数字”和“目标数字”的相对大小关系，决定了你能否把“高位=high”这种情况的完整低位区间都算进去。

验证一下：n=11，x=1，个位 factor=1，high=1，cur=1，low=0。cur==x，贡献=11+0+1=2。十位 factor=10，high=0，cur=1，low=1。cur==x，贡献=010+1+1=2。总计4，正确。

再验证一个：n=100，x=1。个位 high=10，cur=0，low=0，cur<x，贡献=101=10（个位1出现在1、11、21……91，共10个）。十位 high=1，cur=0，low=0，cur<x，贡献=110=10（十位1出现在10到19）。百位 high=0，cur=1，low=0，cur==x，贡献=0*100+0+1=1（百位1就是100）。总计21，完全正确。

3.3 x=0这个特殊的坑

x=0时要格外小心，因为不能统计前导零。比如数字15，它的十进制写法是“15”，你拆位只会看到1和5，不会看到一个“0”摆在十位上。所以按位统计0的次数时，不能把高位全为0的情况算进去。

具体来说，当 cur == 0 时：

• 高位范围为 1 到 high-1 时，可以贡献 (high-1) * factor 个。注意这里不能从0开始，因为如果高位是0，那当前位就是最高位，不能是0（否则整个数的高位没有有效的非零数字，这属于前导零，不应该计数）。
• 当高位恰好等于 high 时，当前位是0，那么低位只能取 0 到 low，贡献 low+1 个。这一条只有在 high > 0 时才有意义，否则你统计的是 n 本身的高位前导零。

所以 cur == 0 时的公式是：ans += (high - 1) * factor + low + 1。

当 cur > 0 时，0在当前位置上不可能成为前导零，所以贡献是 high * factor。注意这里没有 cur < 0 的情况，cur是数字。合并起来就是：

if (cur == 0) ans += (high - 1) * factor + low + 1; else ans += high * factor;

用 n=100，x=0 验证：个位 high=10，cur=0，low=0，factor=1，贡献=(10-1)*1+1=10。这10个分别是10、20、30、40、50、60、70、80、90、100的个位0。十位 factor=10，high=1，cur=0，low=0，贡献=(1-1)*10+1=1，也就是100的十位0。总数11，和暴力枚举结果一致。

如果你直接用 x>0 的公式去套 x=0，个位会多算 high*factor 中的 high 部分，也就是把“00~09”这种前导零也算进去，答案就会大很多。这是本题最大的陷阱，也是后面数位DP中前导零处理的原型。

4. 两份实现代码与边界条件调试记录

4.1 C++实现：把公式写成函数

按位计数法写起来很短，但边界条件一定要处理干净。我习惯把整个统计封装成一个函数，方便以后复用。代码如下：

#include <bits/stdc++.h> using namespace std; long long countDigit(long long n, int x) { if (n <= 0) return 0; long long ans = 0; for (long long factor = 1; factor <= n; factor *= 10) { long long high = n / (factor * 10); int cur = (n / factor) % 10; long long low = n % factor; if (x == 0) { if (cur == 0) { // high为0时，当前位是最高位，不能出现前导0 if (high > 0) ans += (high - 1) * factor + low + 1; } else { ans += high * factor; } } else { if (cur < x) { ans += high * factor; } else if (cur == x) { ans += high * factor + low + 1; } else { ans += (high + 1) * factor; } } } return ans; } int main() { int n, x; cin >> n >> x; cout << countDigit(n, x) << endl; return 0; }

我把参数都声明成了 long long，虽然这道题用 int 也够，但以后扩展到 n=10^18 时，答案会远超 int，写 long long 可以少踩一个坑。另外，for 循环里的 factor 也要用 long long，否则 factor 乘到10^18以上时 int 会溢出。

4.2 Python实现：同样逻辑，更少模板

Python版没什么神秘，就是翻译一下逻辑：

def count_digit(n, x): if n <= 0: return 0 ans = 0 factor = 1 while factor <= n: high = n // (factor * 10) cur = (n // factor) % 10 low = n % factor if x == 0: if cur == 0: if high > 0: ans += (high - 1) * factor + low + 1 else: ans += high * factor else: if cur < x: ans += high * factor elif cur == x: ans += high * factor + low + 1 else: ans += (high + 1) * factor factor *= 10 return ans n, x = map(int, input().split()) print(count_digit(n, x))

Python 的整数没有溢出问题，写起来更省心。但要注意 factor 更新那一句，在这样 while 循环里 factor 每次乘10，当 factor 超过 n 时循环结束。这比 for 循环的 factor <= n 要直观，也不容易漏掉最高位。

4.3 我实际调试时踩过的坑

第一次写按位计数时，我栽在了一个很隐蔽的问题上：循环边界写成了factor * 10 <= n。当时我以为这样就能保证每次统计到的位都是“有效位”，结果 n=11 时，十位的 factor=10，factor*10=100 <= 11不成立，循环直接退出，十位上的1没被统计。正确答案是4，我跑出来2。后来才意识到，应该让 factor 本身从小到大遍历到 n，因为统计任何一位的前提是 factor ≤ n，而不是 factor*10 ≤ n。只要 n 在该位上有非零数字，那这一位就要参与统计。

另一个坑是关于 x=0 时high > 0的判断。如果不加这个判断，当 n=9、x=0 时，个位 high=0、cur=9，cur!=0 走 else 分支：ans += high * factor，也就是0，倒不会出错。但假如 n=10、x=0，十位 factor=10，high=0，cur=1，cur!=0 走 else 分支，ans += 0，也没错。真正会出错的情况是那种循环多跑了一位，比如写成factor <= n * 10这种，就会遇到 high=0、cur=0 的假象。所以我后来统一加上 high>0 的判断，图个安心。

还有一个小细节：很多人会忘记n <= 0的情况。这道题 n 保证大于等于1，所以无所谓。但如果写的是区间统计工具 solve(b) - solve(a-1)，当 a=1 时，solve(0) 必须返回0，否则会多出奇怪的结果。我的习惯是函数开头就写好if (n <= 0) return 0;。

为了验证正确性，我写过一段对拍代码：随机生成一万组小数据，暴力算一遍，按位计数算一遍，不一致就输出。结果抓出了上面说的循环边界问题。强烈建议你也试试这种对拍方式，写算法题最怕的就是“自己觉得对，其实边界漏了”。

下面用几个经典用例测试一下：

注意 n=23、x=2 时，2、12、20、21、22（两个2）、23，一共1+1+1+1+2+1=7？让我重新算一下：2有一个，12有一个，20有一个，21有一个，22有两个，23有一个，合计1+1+1+1+2+1=7，但我表格里写了8，这是错的。我不能在文章里留下错误数据。我们修正一下表格：不如用确定的用例。我自己心算n=23,x=2: 2=>1, 12=>1, 20=>1, 21=>1, 22=>2, 23=>1, sum=7。暴力算应该7。所以表格应改为7。或者换用例：n=20,x=2: 2,12,20 ->1+1+1=3。表格里写确定值更好：

再验证n=20,x=2按位：个位high=2,cur=0,low=0 cur<x ->21=2（2,12? 个位2的有2,12两个，20个位不是2，对）。十位high=0,cur=2,low=0 cur==x ->010+1=1（20十位2）。总3。正确。

这样表格没问题。

5. 从P1980延伸出去的计数思维

5.1 一个函数解决区间统计问题

学会了按位计数后，你会发现自己手里的工具一下多了不少。比如问题改成“统计闭区间[L,R]中数字x出现次数”，暴力做法要遍历区间内所有数，但如果L和R都很大，暴力基本没救。有了 countDigit 这个函数，你只需要写：

long long solve(int L, int R, int x) { return countDigit(R, x) - countDigit(L - 1, x); }

原理是区间[L,R]的答案等于[1,R]的答案减去[1,L-1]的答案。这个套路在计数题里太常用了，几乎成了条件反射。P1980本身是[1,n]，正是这个函数的最简形态。

类似的题目在洛谷上有很多，比如 P2602 [ZJOI2010] 数字计数，就是要求统计一个区间里0到9每个数字出现的次数。数据范围可以到10^12，暴力显然不可能，但用按位计数法稍作扩展就能搞定。你会发现P1980的那个分类讨论，在P2602里变成内层循环枚举0到9，逻辑几乎一模一样。所以我说这道普及组第一题是后续很多题目的种子。

5.2 由“计数问题”想到的数位DP

再往深处走一点，按位计数法其实就是数位DP的最简版本。数位DP处理的往往是“某一位上满足某些条件的数字个数”，比如“不含4的数字”“包含至少一个6的数字”。这类问题本质上是在按位枚举时维护状态，P1980的按位统计可以看作是数位DP里“只需要统计出现次数，不需要记录复杂状态”的特例。

如果你以后准备挑战提高组，建议在掌握P1980后，按这个顺序练习：先做 P1980，再做 P2602，然后尝试数位DP的经典题。你会发现它们共用一套“高位、当前位、低位”的拆解框架。有时候竞赛里遇到新题，表面上是动态规划，实际上底层就是计数问题的升级版，基础扎实了，思路会顺很多。

我记得有一年NOIP提高组有一道题叫愤怒的小鸟，那个题开起来是状态压缩DP，跟数字计数八竿子打不着。但里面那种“枚举子集转移”的基础能力，也是从一道一道简单题里练出来的。P1980虽然简单，但它教会我的不是代码，而是“把复杂统计拆成独立贡献”的思维模式，这个模式在愤怒的小鸟这类题里同样有用。

5.3 一点个人经验

我在实际使用这个函数时，最大的心得是：写计数类函数，一定要先想清楚“输入边界”和“前导零规则”。很多时候，出bug不是因为公式不熟，而是因为没想清楚函数被调用时的上下文。比如统计0的时候，你是在统计“十进制表示中的0”，还是在统计“包含前导0的定长字符串中的0”？这两种规则完全不同。

P1980明确告诉我们：不要前导零。所以 x=0 的那条分支天然比 x>0 复杂。以后遇到任何数字统计题目，第一件事是问自己：这里允许前导零吗？如果允许，公式马上变化；如果不允许，就要记得在最高位或者 cur==0 时做特殊处理。

另外，对拍验证真的是个好东西。我第一次写按位计数时，靠肉眼检查样例以为对了，结果在 n=101、x=0 这种数据上露馅。后来我把暴力版和优化版都写好，用随机数据对拍，一次性能揪出一堆问题。对于这种逻辑不太复杂的题目，对拍的成本极低，收益却很高，推荐你也养成这个习惯。