今天刷题打卡进入第五天我把三道看起来完全不像的题放到同一个清单里求阶乘结果0的个数、判断怪数、找abc数字。很多刚起步的朋友看到“阶乘”第一反应是递归看到“怪数”第一反应是找规律看到“abc数字”第一反应是三重循环。实际动手之后就会发现它们都在考同一件事把数学描述翻译成程序逻辑时先做化简再做枚举先划范围再写循环。这个练习组合很适合刚学编程想进阶的读者也适合准备笔试、机试前专门刷数字规律题的人。我会把我踩过的坑、改过的版本都放出来方便你直接对照。1. 为什么把这三道题放在一起练1.1 题目表面不一样考法是一样的前几天我刷的都是排序、字符串这类题今天突然换成纯数字题刚开始有点不适应。后来在同一个编译器里写完三道题发现它们其实有共同骨架。阶乘末尾0个数这题n!本身会大到离谱不能真算必须先观察0是怎么产生的。怪数判断这题需要先理解数学名词再从因数集合里挑子集本质是枚举加筛选。abc数字这题三位数一共只有900个可以暴力枚举但必须清楚“abc”代表的是a乘100加b乘10加c不是字符串拼在一起。三者在写代码前都要求你先做一个小推导把搜索空间缩小。这种“先数学后编码”的题笔试里很爱出尤其是银行、国企的机试经常混着一堆这类小题。如果平时只刷数组、链表遇到它们会容易慌但只要形成固定套路其实是拿分题。1.2 我固定的三步解题流程我现在遇到数字题一律先走三遍固定流程基本能避免一大半低级错误。第一步在纸上推演。取一个很小的输入比如n10手动把过程列出来确认输出到底长什么样。很多错误都是因为脑内预演和题目本意不一致导致代码写完了才发现方向错了。第二步划定边界。数据范围是1还是0数字是三位数还是允许有前导零n!的中间结果会不会溢出这些边界决定用什么数据类型、循环从哪开始。第三步确定工具。该用循环、递归还是动态规划不要一开始就套模板。这三个动作做完再写代码比上来就敲快得多。我见过太多人看到“阶乘”就递归看到“子集”就回溯最后在小数据能过、大数据集体超时。1.3 三道题的复杂度定位先给个对比表后面展开讲的时候方便对照。题目核心考点搜索空间真正的难点阶乘末尾0因子2和5只看5的个数数学化简怪数判断真因数集合因数数量通常很少子集和判断abc数字三位数拆位100到999共900个题目定义理解这三道题分别代表三种策略阶乘类靠公式怪数类靠搜索abc类靠枚举。不会互相替代但思考路径是共通的。下面我把每个题的实现细节、边界条件和测试数据拆开讲。2. 求阶乘末尾0的个数核心是数因子52.1 为什么不能直接算n!最容易想到的做法是先算n!然后不停对10取余数统计0。我初学时就写过这种代码n10能跑出结果n20就完全不对了。20!已经接近2.43乘以10的18次方纯long long已经存不下如果为了精确性去写大数乘法又会超时。这里的关键是末尾的0不是“算出来”的而是10的因子凑出来的。10等于2乘5阶乘里因子2的个数永远远多于因子5所以末尾0的个数完全由1到n中含有多少因子5决定。举个例子10!等于1乘2乘3一直乘到10因子5出现在5本身和10等于2乘5这两处一共两个5因子所以末尾是两个0。按定义去算10!结果是3628800末尾确实两个0。这个规律一旦确认阶乘本身根本不用算问题变成了计数问题。2.2 数因子5的公式从1到n能被5整除的数有n除以5向下取整个它们至少贡献一个因子5。能被25整除的数贡献两个5但已经在第一步里算过一次所以额外再数n除以25向下取整。能被125整除的数再额外数一次以此类推。写成循环就是不断把n除以5累加def trailing_zeroes(n: int) - int: count 0 while n 0: n // 5 count n return count注意边界n0时0!定义为1末尾没有0循环直接跳过返回0正好正确n5时5!等于120答案应为1n25时5、10、15、20各贡献一个525贡献两个5一共6个程序算出来也是6。我每次写完都会用下面这些手算值做单测0对应05对应110对应225对应6100对应24。这些点全部通过基本就稳了。如果题目给的n特别大用long long接收保险一点虽然多数题n在10的9次方以内int也够但我不想在这种地方被阴。2.3 延伸计算n!最右边的非零位刷“阶乘”关键词时经常关联出另一道题计算n!的最右边的非零位的值。它和末尾0个数是兄妹题。思路是把所有因子2和5先剔掉因为它们组合成10会把个位变成0剩下的数乘积取模10最后再把多出来的2乘回去。我常用的朴素写法能处理n在1000以内的场景def rightmost_non_zero_digit(n: int) - int: res 1 cnt2 0 cnt5 0 for i in range(1, n 1): x i while x % 2 0: x // 2 cnt2 1 while x % 5 0: x // 5 cnt5 1 res (res * (x % 10)) % 10 for _ in range(cnt2 - cnt5): res (res * 2) % 10 return res这段代码的意思是把每个乘数i里的2和5先剥离并计数剩下的部分参与累乘取个位。最后因为因子2的数量总是比5多把多出来的2乘回去结果就是去掉末尾0后的个位数。n10时10!最右非零位是8程序输出8n20时20!最右非零位是4。为什么不直接对阶乘取模10因为比如10!等于3628800直接模10得到0而我们要的是刨掉末尾0之后的个位所以每步拆分是必须的。这个写法不是最优的但最容易理解笔试够用。如果n高达10的9次方就需要用5进制拆位或预计算循环节这个以后单独写。3. 怪数判断一个“丰数子集和”的组合题3.1 怪数到底是什么意思“怪数”在数学里有正式名字weird number。我第一次看到这个中文译名还以为是出题人自己编的其实它是一个正经概念。定义分成两层一个自然数如果它的所有真因数之和大于它本身那它就是“丰数”如果在这些真因数里能挑出若干个数使它们的和恰好等于它本身那它就是“半完全数”。一个数既是丰数又不是半完全数才叫怪数。最小且最经典的怪数是70。70的真因数有1、2、5、7、10、14、35加起来等于74大于70所以是丰数但任取其中几个数都无法凑出70所以不是半完全数。因此70是怪数。按这个标准往下数前几个怪数分别是70、836、4030。要验证更大的数写程序比手算靠谱得多。这里我要提醒一句有些题目里的“怪数”可能不是数学定义而是题目自己发明的一种数比如“各位数字满足某种算式”。如果考试遇到一定先看清楚题目给出的定义。我下面按标准数学定义讲这是最常见的一种。3.2 判断怪数的完整流程判断一个数n是不是怪数分三步。第一步收集n的所有真因数。遍历1到根号n能整除就同时加入i和n除以i最后把n自己去掉因为“真因数”不含自身。第二步求和判断是不是丰数。如果和都不大于n直接返回False。第三步如果前面通过再判断是否存在某些真因数恰好相加等于n。这一步用DFS加剪枝或者用01背包。为什么必须做第三步因为只看“真因数之和大于本身”不够。比如12的真因数是1、2、3、4、6之和为16大于12但1加2加3加6等于12能凑出本身所以12不是怪数只是半完全数。类似的还有18、20等一堆丰数都会被第三步筛掉。这一步的搜索空间其实不大一个数的真因数个数通常很少即使n到10的6次方因数也不会超过240个。我习惯用记忆化搜索避免递归里重复算同一个状态。3.3 代码实现判断单个n是不是怪数下面是我的Python实现用set收集因数再用带记忆的DFS判断是否能用子集凑出目标值。def get_proper_divisors(n: int): divs set() for i in range(1, int(n ** 0.5) 1): if n % i 0: divs.add(i) if i ! n // i and n // i ! n: divs.add(n // i) divs.discard(n) return sorted(divs) def can_sum_to(divs, target): memo {} def dfs(idx, remain): if remain 0: return True if idx len(divs) or remain 0: return False key (idx, remain) if key in memo: return memo[key] memo[key] dfs(idx 1, remain) or dfs(idx 1, remain - divs[idx]) return memo[key] return dfs(0, target) def is_weird(n: int) - bool: divs get_proper_divisors(n) if sum(divs) n: return False return not can_sum_to(divs, n)这段代码里有一个容易被忽略的坑收集因数时i和n除以i可能相等。比如n36时i66只能加一次不能加两次我在代码里加了i ! n // i的判断。同时当i1时n除以1等于n这个n自身也会被加进集合最后通过discard(n)去掉。另一个坑是DFS里的循环顺序最好把因数从大到小排序优先尝试大的数剩余值会快速减小剪枝效率高很多。我实际测试时把divs改成降序后判断一个大数的耗时肉眼可见地下降。如果题目要求输出某个范围内的所有怪数就直接循环调用is_weird怪数没有简单的递增规律只能靠枚举但绝大多数数在第一步“不是丰数”就被淘汰了整体很快。3.4 测试数据与边界给你几个可以直接用来验证的输出。n真因数之和是否丰数能否凑出n结论1216是能1236不是怪数1821是能1269不是怪数7074是不能是怪数836大于836是不能是怪数108否不需要判断不是怪数我建议至少把70、836这两个点写进测试。它们是标准怪数网上资料都会提到。如果程序在70或836上返回False多半是因数收集时把自身也算进去了或者把“半完全数”的条件判断反了。还有一个经验真因数之和等于n的数叫完全数比如28它不是丰数所以也绝不会是怪数如果你在程序里看到某个完全数被输出为怪数那一定是丰数判断写错了。4. abc数字三位数拆位与水仙花变体4.1 先明确题目在说什么“abc数字”在不同题库里意思可能不一样。我最常遇到的定义是找出所有三位数abc满足a的三次方加b的三次方加c的三次方等于100a加10b加c也就是abc本身等于各位数字的立方和。这其实就是大家熟悉的水仙花数但很多题不直接叫水仙花而叫“abc数字”因为公式里正好有三个字母。另一种常见定义是abc等于a!加b!加c!也就是各位数字的阶乘和等于本身。这两种题型的解法几乎一样只是右边的计算从立方改成阶乘。我先按水仙花版本讲最后给变体的改法。做这道题最容易被坑的是把abc当成字符串拼接。比如a1、b5、c3拼出来是153没问题但如果b0字符串拼接可能弄丢前导零而数字a乘100加b乘10加c不会丢。所以我在代码里一律用数学方式算原数。4.2 两种写法拆位枚举和组合拼接第一种写法是枚举三位数本身再拆出百位、十位、个位for num in range(100, 1000): a num // 100 b (num // 10) % 10 c num % 10 if a**3 b**3 c**3 num: print(num)这个写法逻辑很直不容易漏数。缺点是每次循环要做几次除法和取模但900个数完全无所谓。标准输出就是153、370、371、407这四个水仙花数。第二种写法是直接枚举a、b、c再组合成数字for a in range(1, 10): for b in range(0, 10): for c in range(0, 10): num a * 100 b * 10 c if a**3 b**3 c**3 num: print(num)两种写法结果一样我个人更喜欢第二种。理由是a、b、c已经被单独拆好不用做取模运算而且如果要改定义比如改成a的b次方加b的c次方加c的a次方或者改成阶乘和只需要改条件式那一行循环结构完全不用动。4.3 改成阶乘和版本如果题目要求abc数字满足各位阶乘和等于本身先把0到9的阶乘算出来存到数组里再同样枚举。这里有个很多人会忘的知识点0!等于11!等于12!等于2。fact [1] * 10 for i in range(1, 10): fact[i] fact[i - 1] * i for a in range(1, 10): for b in range(0, 10): for c in range(0, 10): num a * 100 b * 10 c if fact[a] fact[b] fact[c] num: print(num)因为这个版本只枚举a从1到9天然保证num是三位数不会出现a0时被当成两位数的干扰项。标准答案里三位数范围内最典型的是145因为1!加4!加5!等于1加24加120等于145。如果你把a也从0开始枚举就一定要加一行num大于等于100的判断否则排查时会多出一些莫名其妙的伪解。这个经验是实打实踩出来的。5. 刷题现场常见错误与排查方法5.1 四个最常见的翻车现场我这次刷题把自己和群里朋友犯过的错误汇总了一下整理成一张速查表。问题现象原因解决方案阶乘末尾0算错n25输出4只统计了能被5整除的个数没算25贡献两个5在循环里反复除以5最右非零位算成0n10输出0直接对阶乘结果取模10得到的是末尾0先把因子2和5剔除再乘怪数判断把所有丰数都输出70输出正确但12也输出没有做子集和判断补上DFS或01背包abc数字漏掉370只输出153循环区间写错或拆位取错明确三位数区间100到999第一行问题最典型。很多人知道要看5的个数但会错误地写成只看n本身能拆出几个5然后忘了统计前面所有5的倍数。输入25时这种写法只会统计25这一个数不会统计5、10、15、20里的因子5结果当然偏小。正确做法是统计1到n中所有5的倍数再按5的幂次累加。第二行问题常见于把“最右非零位”理解成“个位”其实只有当n小于5时它俩才一样一旦n大于等于5阶乘尾部出现0就必须做因子拆分。第三行问题最致命我一开始也是把“真因数之和大于n”作为唯一条件结果输出了一堆丰数后来才补上半完全数判断。第四行纯粹是粗心水仙花的解是153、370、371、407如果漏掉370或371多半是百位拆位写成了num模100而不是num除以10再模10。5.2 几个提升正确率的实测技巧写完代码先别急着提交按下面顺序自查一遍能省很多时间。边界值测试要放在第一位。0、1、5、10、70、836、999这几个数我每道题都会过一遍。边界值能暴露一多半问题。然后是溢出检查如果中间过程出现乘法先估算最大结果。比如最右非零位的代码里只剩2因子时乘回去最多乘几十次不用担心但如果直接算阶乘就不可能不爆。再就是打印调试在循环里print中间变量比如末尾0的累加值、怪数的因数集合和手算结果对比。不要怕print慢900个数的循环随便打印。还有一个很实用的习惯如果只修改了题目条件比如从水仙花改成阶乘和但答案还是原来那四个数说明新条件根本没触发分支。这时候要检查新条件里的变量是不是写成了老变量。我就在这个上面浪费过十分钟条件式里明明要阶乘手一快写成了三次方输出自然不变。根据我个人经验这类“枚举加数学”的题最怕的不是算法难而是定义没吃透。求阶乘末尾0的个数“0的个数”指十进制末尾的0不是二进制怪数里的“真因数”不含自身abc数字里的“abc”是三位数不是字符。三个定义各差一个字答案就天差地别。我把这些写在笔记本最前面以后看到类似题先花半分钟把这些词圈出来再动手比直接敲代码靠谱得多。最后分享一个扩展方向如果把这三题的输入范围都放大到10的18次方朴素写法都会失效。阶乘末尾0可以用二分答案怪数判断需要更高效的子集和技巧abc数字则基本只能打表预处理。我准备下次专门练一遍大范围版本再写一篇对比记录。今天先到这里代码都在上面可以直接复制到本地跑一遍。