洛谷 B4007 / B4411 / B4035 计数、优美的数字与美丽数字——余数与数学之美 摘要B4007 统计数字 k 在 1 到 n 中出现的次数B4411 统计所有位都相同的数的个数B4035 统计是 9 的倍数但不是 8 的倍数的数的个数。三道题共享两个核心操作逐位拆解%10取个位、/10去个位和取余判断%k 0判断整除。很多同学在做这些题时第一次真正理解了余数——当被除数小于除数时余数等于被除数本身而不是 0。三道题的名称——计数、优美、美丽——都在邀请我们从人文角度欣赏数学。本文从伪代码题解出发延伸到余数的数学本质、9 的数位和整除规则、重码数Repdigit的数论性质以及从毕达哥拉斯到 Erdős 的数学美传统。题目链接B4007 计数 | B4411 优美的数字 | B4035 美丽数字 目录 前言 三道题在考什么 B4007计数 思路 伪代码 关键点✨ B4411优美的数字 思路 伪代码 关键点 B4035美丽数字 思路 伪代码 关键点⚖️ 三题对比⚠️ 注意事项 延伸数学之美——从余数到数论 余数的本质被除数小于除数时✨ 9 的魔力数位和与整除规则 重码数Repdigit所有位相同的数 数学美从毕达哥拉斯到 Erdős 三道题的数学内核 延伸阅读文献 前言这篇题解没有源代码只有伪代码。作为一名信奥教练我不提倡复制粘贴。我见过太多学生搜到题解、复制、粘贴、提交、AC——代码跑通了脑子没跑通。下次遇到变体题还是不会。伪代码剥掉了语言的壳只留算法的骨架。你看不到#include看不到cin、cout看不到那些让你以为我会了的语法细节。你能看到的只有这一步做什么、下一步做什么、为什么这么做。如果你是路过的友友已经在这道题上挣扎了很久——先去喝杯水回来重新看看自己卡在哪一步。是没读懂题意是思路方向偏了还是代码有 bug 但逻辑其实对大多数时候不是不会是走偏了。偏了不可怕可怕的是偏了之后直接放弃去抄一份能 AC 的代码。抄完你以为你懂了其实你只是搬了别人的结论。除非你时间真的紧张——比赛临近、作业要交——那种情况先 AC 再说能理解。但平时练习给自己一点耐心。先自己想、自己写、自己调跑不过了再来看伪代码你的思路和这里差在哪一步。那一步就是你真正学到的东西。 三道题在考什么三道题都是对数字做某种判断然后计数但判断的依据截然不同B4007 计数B4411 优美的数字B4035 美丽数字判断什么某个数字 k 出现了几次所有位是否都相同是 9 的倍数但不是 8 的倍数核心操作逐位拆解 比较逐位拆解 一致性检查取余判断整除性数学概念数字频率重码数Repdigit整除与互斥条件难度入门入门入门B4007 把每个数的各位拆开数某个数字出现了几次。B4411 把每个数的各位拆开检查它们是否全相同。B4035 不拆数字直接用取余判断整除性。前两题是逐位操作第三题是整体取余。三道题的名称——计数、优美、美丽——都不约而同地用了审美词汇。这不偶然数学家和数学教育者一直认为数学的美感应该被体验而不仅仅是被计算。 B4007计数 B4007 思路遍历 1 到 n 的每个数对每个数用%10取个位、/10去个位逐位检查是否等于 k累加计数。 B4007 伪代码读取 n, k 计数 0 对 i 1 到 n: temp i 当 temp 0: 如果 temp % 10 k: // 取个位 计数 temp temp / 10 // 去掉个位 输出 计数 B4007 关键点逐位拆解。%10取个位/10去个位循环直到数为 0。这是数字位操作的基础。用样例 n25, k2 追踪数各位含 2 的个数累计110022113~11—01121, 21213~19—02202, 013212, 114222, 226232, 317242, 418252, 519输出9。22 贡献了 2 次。数字 22 的十位和个位都是 2所以%10检查个位2计数/10后变成 2再%10检查2计数总共 2 次。逐位拆解自然地处理了同一个数中多次出现的情况。✨ B4411优美的数字 B4411 思路遍历 1 到 n 的每个数取个位作为参考数字然后逐位检查所有位是否都等于参考数字。如果全部相同就是优美的。代码取i % 10个位作为参考single_num然后从个位开始逐位检查。如果任何一位不等于single_num立刻break。如果temp 0所有位都检查过且都相同则计数。 B4411 伪代码读取 n 总数 0 对 i 1 到 n: temp i 参考数字 i % 10 // 取个位作为参考 当 temp 0: 当前位 temp % 10 如果 当前位 ! 参考数字: 跳出循环 // 发现不同不优美 temp temp / 10 如果 temp 0: // 所有位都检查过全相同 总数 输出 总数 B4411 关键点全相同的判断技巧。取一个位作为参考逐位比对。如果中途发现不同就 breaktemp 不为 0如果全部相同循环正常结束temp 变为 0。用temp 0作为全相同的标志。用样例 n6 追踪数各位参考数字全相同累计111✓1222✓2333✓3444✓4555✓5666✓6输出6。1-6 都是一位数自然全相同。n2025 的情况。1-9 是 9 个11-99 是 9 个111-999 是 9 个1111 是 1 个2222 2025 不算。999128。这些数叫什么所有位都相同的数在数论中叫重码数RepdigitRepeated DigitRepdigit — Wikipedia。1, 2, …, 9, 11, 22, …, 99, 111, 222, …, 999, 1111, … — 每个位都是同一个数字的重复。延伸部分会展开讲。 B4035美丽数字 B4035 思路读入 n 个数对每个数检查两个条件是 9 的倍数%9 0且不是 8 的倍数%8 ! 0。两个条件都满足才算美丽。 B4035 伪代码读取 n 美丽数计数 0 对 i 1 到 n: 读取 temp 如果 temp % 9 0 且 temp % 8 ! 0: 美丽数计数 输出 美丽数计数 B4035 关键点取余判断整除。a % b 0意味着 a 能被 b 整除。a % b ! 0意味着不能。两个条件用且连接——必须同时满足。用样例[1, 9, 72]追踪数%9 0?%8 ! 0?美丽?11%91≠0 → 否—否99%90 → 是9%81≠0 → 是是7272%90 → 是72%80 → 否否输出1。72 为什么不美丽72 是 9 的倍数8×972但也是 8 的倍数9×872。题目要求是 9 的倍数但不是8 的倍数——两个条件缺一不可。被除数 除数时的余数。很多同学在这里第一次真正理解了余数。比如 1 % 8 等于多少直觉上8 除不尽 1但余数不是 0——是 1。因为 1 ÷ 8 0 余 1。当被除数小于除数时商为 0余数等于被除数本身。这个看似简单的概念是整除判断的基础。⚖️ 三题对比B4007 计数B4411 优美的数字B4035 美丽数字操作对象数字的一位数字的每一位整个数字核心操作%10/10逐位拆解%10取参考 逐位比对%9和%8整除判断计数条件某位 k所有位 参考位是 9 倍数且非 8 倍数数学概念数字频率重码数Repdigit整除性与互斥条件美在哪数字出现在多少个数里所有位和谐统一恰好满足双重条件复杂度O(n × d)O(n × d)O(n)B4007 和 B4411 都在逐位拆解——把一个多位数拆成一位一位的。B4035 不拆直接对整个数取余。前两题是微观操作看每一位第三题是宏观操作看整个数。⚠️ 注意事项余数基础被除数 除数时余数 被除数这是很多同学的第一个原来如此时刻。1 % 8 1不是 03 % 9 3不是 07 % 8 7不是 0。因为 1 ÷ 8 0 余 1。a % b 0只有在 a 是 b 的倍数或 a0时才成立。当 a b 且 a 0 时a % b a ≠ 0所以 a 不是 b 的倍数——这是正确的。B4007 的 22 贡献两次逐位拆解会自然地把 22 拆成两个 2各检查一次。不需要特殊处理同一个数中多次出现的情况。B4411 的temp 0判断循环正常结束所有位都相同时 temp 变为 0中途 break发现不同时 temp 不为 0。用temp 0作为全相同的标志是一种简洁的写法但可读性见仁见智——更直观的写法是单独设一个all_same布尔标志。B4035 的且逻辑%9 0 %8 ! 0两个条件必须同时满足。如果用||或72 也会被判为美丽因为 72%90 成立这是错的。B4035 的数据范围n, a_i ≤ 10⁵O(n) 遍历即可无需优化。 延伸数学之美——从余数到数论你说这三道题的名称——计数、优美、美丽——“似乎都在让大家从人文角度去欣赏数学的魅力”。没错而且这个传统从 2500 年前就开始了。 余数的本质被除数小于除数时很多同学做 B4035 时第一次碰到了这个问题1 % 8等于多少直觉说8 除不尽 1有人猜 0除不尽就是 0 余数有人猜 -7差 7 才到 8。但答案是1。因为除法的定义是被除数 商 × 除数 余数其中 0 ≤ 余数 除数。1 0 × 8 1 → 商0, 余数1 3 0 × 9 3 → 商0, 余数3 7 0 × 8 7 → 商0, 余数7当被除数 除数时商为 0余数 被除数本身。这不是特殊规则是除法定义的直接推论。表达式商余数含义17 % 53217 里有 3 个 5剩 28 % 8108 里有 1 个 5不剩 → 整除3 % 8033 里没有 8剩 31 % 9011 里没有 9剩 1余数 ≠ 0 意味着不整除。当 a b 且 a 0 时a % b a ≠ 0所以 a 不是 b 的倍数。这是 B4035 中%8 ! 0判断的逻辑基础。这个概念在数学中叫模运算Modular Arithmetic是数论的基础工具。高斯在 1801 年的《算术研究》中系统化地建立了模运算理论从此它成了现代密码学RSA、计算机科学哈希函数、竞争编程数论题的共同语言。✨ 9 的魔力数位和与整除规则B4035 判断9 的倍数B4007 和 B4411 都在逐位拆解数字。这两件事之间有一个深刻的数学联系一个数能被 9 整除当且仅当它的各位数字之和能被 9 整除。The Magic of Numbers — Utah Math Circle20 Cool Math Facts — CueMath为什么因为10 ≡ 1 (mod 9)——10 除以 9 余 1。所以 10 的任何次方除以 9 都余 110 9×1 1 → 10 ≡ 1 (mod 9) 100 9×11 1 → 100 ≡ 1 (mod 9) 1000 9×111 1 → 1000 ≡ 1 (mod 9)所以一个数比如 576 5×100 7×10 6×1对 9 取余576 mod 9 (5×1 7×1 6×1) mod 9 (576) mod 9 18 mod 9 0576 的各位数字之和 5761818 是 9 的倍数所以 576 是 9 的倍数。Base-b Digit Sum Function特殊数学性质 — CSDN这意味着B4007 的逐位拆解和B4035 的取余判断整除在数学上是连通的——逐位拆解数字求和就等价于对 9 取余。你在 B4007 里数 2 出现了几次和判断一个数是不是 9 的倍数用的是同一套位值数学。整除规则原理和三道题的关系能被 9 整除 ↔ 各位之和能被 9 整除10 ≡ 1 (mod 9)B4035 判断 9 的倍数能被 3 整除 ↔ 各位之和能被 3 整除10 ≡ 1 (mod 3)同理能被 2 整除 ↔ 末位是偶数10 ≡ 0 (mod 2)—能被 5 整除 ↔ 末位是 0 或 510 ≡ 0 (mod 5)—9 的整除规则之所以特别是因为 10 ≡ 1 (mod 9)——每一位的权重都是 1所以各位直接相加就行。这就是为什么 9 在整除规则中独树一帜。 重码数Repdigit所有位相同的数B4411 的优美数字——所有位都相同的数——在数论中有一个正式名字重码数RepdigitRepeated DigitRepdigit — Wikipedia。重码数的序列是1, 2, 3, …, 9, 11, 22, 33, …, 99, 111, 222, …, 999, 1111, …一个 d 位的重码数可以写成R(d, r) r × (10^d - 1) / 9 其中 d 是位数r 是重复的数字1-9比如 222 2 × (10³ - 1)/9 2 × 999/9 2 × 111 222。重码数有一些有趣的数论性质Repdigit and Repunit — Research性质例子说明全由 1 组成的重码数叫重一数Repunit1, 11, 111, 1111, …“Repeated Unit”1966 年命名Repunit — Wikipedia重码数要为质数必须是重一数且位数为质数11 是质数2 位2 是质数22 2×11 不是质数不是所有质数位的重一数都是质数111 3×37 不是质数3 位3 是质数但 111 不质位数为质数是必要非充分条件重码数的数字和 位数 × 重复数字222 的数字和 3×2 6和 9 的整除规则联动B4411 答案的数学公式。不超过 n 的重码数个数可以算出来对每个位数 d1 到 n 的位数每个重复数字 r1 到 9如果 R(d,r) ≤ n 就算一个。n2025 时1 位 9 个 2 位 9 个 3 位 9 个 4 位只有 1111 ≤ 2025 一个 28。你不用遍历 1 到 2025 每个数直接枚举位数和重复数字就能算出来——从 O(n) 优化到 O(9 × log n)。 数学美从毕达哥拉斯到 Erdős三道题的名称——计数、优美、美丽——用了审美词汇。这不是偶然。数学家和数学教育者一直相信数学的美感应该被体验而不仅仅是被计算。人物时代名言/观点毕达哥拉斯公元前 500 年“万物皆数”All is number——第一个把数学和美等同的人柏拉图公元前 400 年“不懂几何者不得入内”——数学是理解真理的前提欧拉18 世纪e^(iπ)10——被公认为最美丽的数学公式哈代20 世纪“数学家的模式如画家或诗人一样必须是美的”A Mathematician’s ApologyErdős20 世纪“上帝有一本证明之书里面收录了每个定理最优美的证明”哈代在《一个数学家的辩白》中写道 Beauty is the first test: there is no permanent place in the world for ugly mathematics.美是第一道考验丑陋的数学在世界上没有永久的位置。——他说的不只是大定理也包括你今天写的每一行代码里的数学逻辑。B4411 的优美数字——所有位都相同——是一种对称美。B4035 的美丽数字——恰好满足两个条件——是一种平衡美。B4007 的计数——数字在序列中出现多少次——是一种规律美。三种美恰好对应数学审美的三个维度。 三道题的数学内核题表面是数学本质是美在哪B4007 计数数数字 k 出现几次位值制——10^k 的权重规律美数字在序列中的频率B4411 优美的数字所有位是否相同重码数——r×(10^d-1)/9对称美重复与统一B4035 美丽数字是 9 倍数非 8 倍数模运算——10 ≡ 1 (mod 9)平衡美双重条件的精确交集三道题共享的数学基础是位值制Place Value System——一个数的值取决于每个数字在哪个位置。B4007 利用位值制把数字拆开B4411 利用位值制检查一致性B4035 的 9 整除规则本身就是位值制的数学推论。位值制是人类发明的最伟大的数学技术之一。没有它我们还在用罗马数字做加减法——MCMXCIV CCLXVII ? 有了位值制同样的运算是 1994 267 2261——逐位计算进位即可。你在三道题里用的%10和/10就是在利用位值制——每一位的权重是 10 的幂。 延伸阅读文献论文A. H. Beiler.Recreations in the Theory of Numbers. Dover, 1966. Repunit — Wikipedia —— Repunit一词的起源重码数与重一数的数论入门。P. Patel et al.Patterns obtained from digit and iterative digit sums of Palindromic, Repdigit and Repunit numbers. Global Journal of Pure and Applied Mathematics, 2016. Research Publication —— 重码数与重一数的数字和模式研究。C. F. Gauss.Disquisitiones Arithmeticae算术研究. 1801. —— 模运算理论的奠基之作数论的经典。在线资源洛谷.B4007 [GESP202406 二级] 计数. https://www.luogu.com.cn/problem/B4007洛谷.B4411 [GESP202509 二级] 优美的数字. https://www.luogu.com.cn/problem/B4411洛谷.B4035 [GESP202409 一级] 美丽数字. https://www.luogu.com.cn/problem/B4035The Magic of Numbers — Utah Math Circle. https://www2.math.utah.edu/mathcircle/notes/magicnumbers.pdf —— 9 的整除规则证明含位值制与模运算。20 Cool Math Facts That Will Change the Way You See Numbers — CueMath. https://www.cuemath.com/blog/20-cool-math-facts/ —— 数学趣味知识含 9 的数字和自检。The Base-b Digit Sum Function — Jupiter Science. https://jupiterscience.com/… —— 位值制与整除规则的数学原理。Repdigit — HandWiki. Wikipedia —— 重码数百科条目含数论性质。Repunit — Wikipedia. Wikipedia —— 重一数百科条目含质数判定。特殊的数学性质 — CSDN. https://blog.csdn.net/ke_wu/article/details/144300038 —— 数模 9 等于各位数之和模 9 的中文解释。推荐教材G. H. Hardy.A Mathematician’s Apology. Cambridge University Press, 1940. —— 哈代关于数学美的经典论述“丑陋的数学没有永久位置”。I. Niven.Numbers: Rational and Irrational. MAA, 1961. —— 数论入门经典含整除性与模运算。A. H. Beiler.Recreations in the Theory of Numbers. Dover, 1966. —— 数论趣味读物重码数与重一数的全面介绍。M. Du Sautoy.The Music of the Primes. HarperCollins, 2003. —— 从质数分布到数学美通俗数学读物。本文标签#算法 #数论 #余数 #整除规则 #重码数 #位值制 #数学美 #洛谷题解 #信奥 #C #入门本文首发于CSDN作者HugoStudio_SWAN