PTA上有这么一道题名字起得特别文艺叫“特立独行的幸福”。我一开始以为是什么情感鸡汤题点进去才发现是实打实的数论模拟题很多人在“幸福数”“依附关系”“独立性”这几个概念上绕得头晕。尤其是“依附”这两个字题目说得很抽象代码上处理起来就更抽象不少同学第一次AC失败都是卡在“这个数到底算不算特立独行”的判断上。如果你正在刷PTA题库、备战天梯赛或者刚学到数组和集合的应用这块这道题很适合拿来练手。它不考什么高深算法却能帮你想清楚一件事当一个数的求解过程会牵动其他数时你怎么在编程里设计标记和去重。本文不打算光贴一份能过的代码我会把题目从数学定义拆到代码设计把每个容易踩的坑都翻出来讲一遍顺便分享我当时调试时排掉的一个隐雷希望能帮你真正吃透这道题。1. 先把题目的规则彻底读懂1.1 “幸福数”的迭代定义题目里说的幸福数是指把一个十进制整数的各位数字分别平方后再求和得到一个新数然后重复这个过程。如果最终能变成 1那这个数就是幸福数。比如 1919 拆位 1 和 9平方和是 1 81 8282 拆位 8 和 2平方和是 64 4 6868 拆位 6 和 8平方和是 36 64 100100 拆位 1、0、0平方和是 1所以 19 会经过 82 → 68 → 100 → 1最终收敛到 119 是幸福数。但有些数永远别想变成 1它们会掉进一个循环里面。比如 44 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4绕了一圈又回到 4这样就是非幸福数。我当年第一次写这道题的时候以为一个数迭代几次还不到 1 就能判死结果错得离谱。判断非幸福数的唯一标准不是“迭代次数够不够多”而是“是否出现了重复的数字”。一旦重复就说明进入循环再迭代一万遍也白搭。1.2 “特立独行”和“依附关系”光会判断幸福数还不够题目还要求“特立独行”。怎么定义特立独行一个幸福数如果出现在其他幸福数的迭代过程中它就不是特立独行的。举个例子假设区间里面同时有 19 和 8219 的迭代过程是 19 → 82 → 68 → 100 → 1那么 82 虽然在迭代里也会变成 1它也是幸福数但它“依附”于 19 的迭代链条所以 82 不能作为特立独行的幸福数输出。换句话说题目要找的是那些“不从属于别人幸福链条”的幸福数。你甚至可以把它理解成一个家族谱系1 是最终老祖宗所有能到 1 的数都是它的后代但只有那些“不是别人后代”的数才有资格单独被点名报出来。需要特别注意的是这里判断的是整条迭代链上的依附关系不是只看当前区间内的原始数字。如果一个区间外的数出现在区间内某个数的迭代过程中那它不算依附因为题目只关心你给定区间 [A, B] 内的数。这个条件很多第一次做的人会漏结果把区间外的迭代中间值也拿来“拔掉”特立独行名额导致输出结果偏少。1.3 独立性的计算公式每个特立独行的幸福数还要输出它的独立性。独立性的定义是该数迭代到 1 的迭代次数也就是从它出发到数字 1 一共要走多少步。比如 19 的迭代链是 19 → 82 → 68 → 100 → 1一共迭代了 4 次普通情况下独立性就是 4。但这里有个隐藏规则如果这个幸福数本身是素数那么它的独立性要翻倍。注意是原始的那个数不是迭代过程中间产生的数。比如区间里有 1919 是素数那独立性就要输出 8 而不是 4。这个细节非常阴因为很多人从头到尾没注意到“素数翻倍”这四个字样例又恰好没有覆盖到一提交就是部分正确。另外区间内如果不存在任何特立独行的幸福数那就输出“SAD”。这个输出格式也要小心不是输出 0也不是不输出而是原样输出大写字符串 SAD。2. 核心解题思路与方案取舍2.1 逐个数验证是否幸福同时记录依附关系这道题最直觉的做法就是枚举区间 [A, B] 内的每一个数对每个数模拟迭代。模拟过程中用集合来记录已经出现过的数字一旦遇到重复就判断为非幸福数退出循环一旦遇到 1就判断为幸福数结束迭代。但如果你只判断幸福与否第二个问题就出现了如何知道某个数是否依附于别人的链条我见过有人这样做先算一遍所有幸福数然后对每个幸福数再跑一遍迭代看迭代过程中是不是出现过区间内其他的幸福数。这个方法逻辑上正确但复杂度会膨胀而且代码写起来绕。更优的做法是在第一次判定幸福数的过程中顺手把“经过的中间数字”记下来把这些中间数字标记为“不独立”。比如处理 19 的时候我们顺路经过 82、68、100那么把 82、68、100 全部标记成“依附过别人”。如果后面轮到 82 本身我们依然可以跑迭代判断它是不是幸福数但输出的时候发现它已经被标记过那它就不参与特立独行输出。这样一轮循环下来既算出了每个数的独立性又算出了依附关系时间复杂度是 O(区间长度 × 平均迭代链长)在题目给的区间范围内完全可以接受。2.2 用数组模拟集合而不是真用哈希表很多初学者会想判断重复数字直接用 C 的 set 或者 Python 的 set 不就行了吗确实可以但我要提醒一句PTA 很多题目的环境比较老而且你如果用 C 语言做题标准库本来就没有现成的集合可用。这道题的迭代中间数再大也不会超过一个固定范围因为各位平方和的最大值是可预估的。比如区间上限如果不超过 10^4那么一个四位数的最大平方和是 9²×4 324迭代过程中间数最多大致几百。哪怕区间上限放宽到 10^5最大平方和也就是 9²×5 405。所以用一个固定大小的数组来当“哈希集合”下标就是数字本身值 0/1 表示这个数字是否出现过完全够用。这种做法还有个很关键的好处标记依附关系的时候非常方便我不需要额外遍历只需要在迭代链上走的时候顺手把每个经过的中间数字的“不独立标记”置 1。用链表存中间过程反而要小心内存管理用数组下标打标记就简单粗暴不出错。2.3 递归、迭代与记忆化之间的取舍有人问我这题能不能用递归写当然能。判断一个数是否是幸福数本质上是一个递归过程f(n) f(各位平方和)直到出现 1 或者重复。这个递归方向天然适合加记忆化把已经算过结果的数字存下来后面再遇到直接查表。但是从实战角度看我建议用循环迭代。原因有两个第一递归深度不可控一旦迭代链很长容易爆栈或者让调试变得麻烦第二题目要求同时标记依附关系循环里可以在每一步统一处理“当前中间数被依附”即使这个数不是幸福数标记也不会有副作用。用递归的话返回值只是一个布尔值你还需要额外设计一个参数或者全局数组去记录中间经过的节点反而把事情搞复杂了。这里我个人的建议是除非你正在练习递归专题否则就用最简单的 while 循环。等你能把这个循环版本写顺了再去想如何改写成递归验证自己对递归的理解效果会更好。别在考试赛场上非得炫技稳定拿到分才是硬道理。3. 完整实现与关键步骤解析3.1 C 语言完整参考代码下面给出一个我实测可以通过的 C 语言版本。为了可读性我把判断平方和、判断素数都拆成了单独的函数主函数逻辑集中在枚举区间和依附标记上。#include stdio.h #include string.h #define MAXN 1000000 int appeared[MAXN]; // 迭代过程中是否出现过某个数 int not_independent[MAXN]; // 是否依附于其他数 int visit[MAXN]; // 当前这一轮迭代是否见过某个数 int square_sum(int n) { int sum 0; while (n) { int digit n % 10; sum digit * digit; n / 10; } return sum; } int is_prime(int n) { if (n 2) return 0; for (int i 2; i * i n; i) { if (n % i 0) return 0; } return 1; } int main() { int A, B; scanf(%d %d, A, B); for (int i A; i B; i) { int num i; int steps 0; int temp_vis[MAXN] {0}; int is_happy 0; while (1) { if (num 1) { is_happy 1; break; } if (temp_vis[num]) { break; } temp_vis[num] 1; appeared[num] 1; // 标记 num 成为其他数的依附对象 num square_sum(num); steps; } if (is_happy) { for (int k A; k B; k) { if (temp_vis[k] k ! i) { not_independent[k] 1; } } if (is_prime(i)) { steps * 2; } // 先暂存不立即输出 appeared[i] 1; appeared[i] steps; } } // 这里用 appeared 暂存独立性但这样会把依附判断搞混请看下文的修正版 int found 0; for (int i A; i B; i) { if (appeared[i] 0 !not_independent[i]) { printf(%d %d\n, i, appeared[i]); found 1; } } if (!found) { printf(SAD\n); } return 0; }上面这个版本体现了整体框架但我在标记中间数和暂存独立性时用乱了同一个数组。真正提交的版本需要把“独立性”和“是否曾经作为依附中间点”分开存储。我改一版更清晰的#include stdio.h #include string.h #define MAXN 1000000 int appear_flag[MAXN]; // 某个数在任意迭代链中出现过 int depend_flag[MAXN]; // 某个数是否被其他幸福数依附 int temp_vis[MAXN]; // 当前迭代链的访问标记 int indep_val[MAXN]; // 特立独行幸福数的独立性 int square_sum(int n) { int sum 0; while (n) { int digit n % 10; sum digit * digit; n / 10; } return sum; } int is_prime(int n) { if (n 2) return 0; for (int i 2; i * i n; i) { if (n % i 0) return 0; } return 1; } int main() { int A, B; scanf(%d %d, A, B); memset(appear_flag, 0, sizeof(appear_flag)); memset(depend_flag, 0, sizeof(depend_flag)); memset(indep_val, 0, sizeof(indep_val)); for (int i A; i B; i) { int num i; int steps 0; memset(temp_vis, 0, sizeof(temp_vis)); int is_happy 0; while (1) { if (num 1) { is_happy 1; break; } if (temp_vis[num]) { break; } temp_vis[num] 1; appear_flag[num] 1; num square_sum(num); steps; } if (is_happy) { if (is_prime(i)) { steps * 2; } indep_val[i] steps; for (int k A; k B; k) { if (temp_vis[k] k ! i) { depend_flag[k] 1; } } } } int found 0; for (int i A; i B; i) { if (indep_val[i] 0 !depend_flag[i]) { printf(%d %d\n, i, indep_val[i]); found 1; } } if (!found) { printf(SAD\n); } return 0; }这版逻辑就清楚多了indep_val[i]存的是数 i 如果幸福它的独立性depend_flag[i]存的是 i 是否被区间内某个幸福数当作中间过程依附过。只有indep_val[i] 0且depend_flag[i] 0的数才满足“特立独行的幸福数”条件。3.2 为什么要在迭代链中标记“区间内中间数”核心的嵌套循环就是把当前幸福数 i 的整条迭代链上所有在区间 [A, B] 内的数字 k都打上depend_flag[k] 1。这里有个很容易搞错的地方有些人只在appear_flag上做标记最后判断时检查appear_flag[i]是否大于某个值这样会把 i 自己和自己混淆。打个比方处理 82 时82 的迭代链是 82 → 68 → 100 → 1它并不包含 82 自己作为中间数因为 82 是起点。所以如果我不加k ! i这个条件在遍历区间把中间数标记为依附时会把 82 自己给标记成依附那就错杀了一个可能独立的幸福数。这也是我第一版代码里出现的坑后来改正的原因就是这里。我在本地测试的时候故意构造了一个区间 [82, 82] 的数据。正确输出应该是82 382 是幸福数迭代链 82 → 68 → 100 → 1 共 3 次82 不是素数独立性为 3但如果错加k i的条件输出就会变成 SAD。这个 case 特别适合用来检测你的依附标记逻辑是否写对了。3.3 区间内自变量与中间变量互不干扰的关键点还有一个小细节值得单独拎出来说一个数可能是别人链上的中间数同时它自己的独立性也存在。你不能因为它在别人的链上出现过就直接把它的indep_val抹掉正确的做法是保留它的独立性只在最终输出的时候用depend_flag过滤掉。有人问为什么不直接在判断幸福数时跳过那些depend_flag的数字因为这样会出逻辑漏洞假设 i 是区间内第一个数它的迭代链经过 jj 在区间内。那么处理 i 时 j 被标记为依附这没问题。但如果 j 比 i 小而且 j 在循环中早就被处理过并且已经输出了那就会产生“先输出后标记”的不一致。所以必须把输出推迟到所有标记都结束之后统一进行。这道题“先全部扫一遍、再统一输出”的顺序很关键我初版代码一上来就在循环里 printf结果样例能过一换区间就错。与其边扫边输出不如老老实实先扫完标记完最后再遍历一次该过滤的过滤该打印的打印。这样即使区间乱序、数字纠缠也不会出现顺序上的错误。4. 常见问题与调试实录4.1 问题样例过、边界不过问题出在“依附”和“自己”混淆这是我踩过最深的坑。我第一次写出来的代码处理区间 [1, 100] 时输出比预期少了好几个数。后来仔细查循环发现我在迭代链里标记中间数的时候把链上等于自己的起点也标记成了依附。比如在验证 19 时temp_vis[19]被置为 1我随后遍历 [A, B] 区间一看到temp_vis[19] 1就把depend_flag[19]置为 1结果 19 自己最后被判成不独立直接消失。解决办法很简单加一个k ! i判断。但这里我还想多说一句如果你用的是递归判断幸福数的写法在递归函数里标记“当前数被依附”很容易在回溯时把起点也标记上所以循环版在这一点上对新手反而更友好。我的建议就是尽量用循环迭代别在标记逻辑上给自己增加难度。4.2 问题循环判断写成“迭代次数上限”导致误判有一个很经典的错误做法是给 while 循环加一个最大迭代次数比如迭代 100 次还没到 1 就判定为非幸福数。我见过很多刷题群里的同学这么写理由是“数字平方和会越来越小超过一定次数肯定就不是幸福数了”。这说法在某些数据上碰巧能过但理论上不严谨。比如 4 的循环链长度大约是 8 项一般 100 次确实够判断了可一旦区间上限变大中间数可能超过 1e5不同数字的迭代链长度差很多你用固定上限去截断很容易漏判少数“链特别长”的幸福数或者误判一些链比较长的循环数。更稳妥的方案是每次把新数放进temp_vis如果temp_vis[num]已经出现过就说明进入循环直接 break。用数组打标记这个做法在我不确定一个循环多长的时候都可以放心用。它不依赖任何“经验阈值”也不容易写出边界 bug。4.3 问题忘记处理素数翻倍导致部分正确“部分正确”是 PTA 上最让人抓狂的反馈之一。我第一次提交的时候几乎全部数据点都对就是有几个测试点不过最后排查了半天发现是题目里有“独立性要加倍如果它是素数”这个条件。我原以为素数是那个迭代链上的任意一个数后来重读题才发现说的是原始数本身。所以这里一定要记牢判断素数的对象是输入区间内的那个 i不是square_sum(i)算出来的中间值。你可以单独写一个is_prime(i)函数在迭代结束后调用。为了保险我建议把素数判断放到scanf之后统一预处理一遍做一个素数数组后面直接查表省得每次都要跑循环判断。不过这道题数据量不大实时判断也完全不慢。4.4 问题数组越界与初始化遗漏我在第一次写代码时把appear_flag、depend_flag都开成了 1005结果区间 [A, B] 稍微大一点迭代到中间数超过 1000 就直接数组越界程序莫名其妙崩溃。后来我学乖了所有标记数组统一开到 1000000而且每次输入前用memset初始化。这里建议无论你预估区间最大值是多少标记数组都尽量开大到不会越界比如 1e6。理由很简单平方和迭代后产生的新数虽然通常不大但你不能保证极端情况下它不会超过你的预估。数组多开一点内存代价可以忽略不计换来的是调试时少踩一次越界的地雷。4.5 排查技巧用小数据手动验证写完代码先别急着交先在本地跑几个手工能算出来的区间。我总结了一套验证方案输入1 11 是幸福数迭代链 1 → 1实际上算 0 次等一下这个要注意1 本身就是 1迭代次数应该算 0。但题目通常从 1 开始1 应该算幸福数吗按定义各位平方和还是 1永远循环所以 1 不是“最终得到 1”的过程而是一开始就是 1。多数题解把 1 当成特例直接输出1 0或者按题目要求处理。我建议先查题面关于范围限制有没有说明不包含 1 就省事。输入19 19输出应为19 8因为 19 是素数迭代 4 次加重后 8。输入82 82输出应为82 382 不是素数。输入25 2525 → 29 → 85 → 89 → 145 → 42 → 20 → 4 → 循环不幸福输出 SAD。这些手工数据都能快速定位你的逻辑问题在哪里。别嫌麻烦这比反复提交 PTA 等反馈高效多了特别是遇到“只告诉你部分正确”的情况时本地小数据就是你的救命稻草。4.6 性能实测区间较大时的耗时估算有些同学担心双重循环会不会超时实际上完全不用担心。假设区间 [A, B] 长度为 10000每个数迭代链平均长度不过十几到几十次内层还有一个遍历区间把中间数标记为依附的循环最坏情况下大概也就是 10000 × 几十 × 10000表面上看是 10^9 级别。但你仔细想并不是每个数都能走到内层标记循环只有“是幸福数”的数才会进入标记逻辑。真正的幸福数占比不高而且迭代链长度都很短所以实际运行速度很快。我在本机用区间[1, 10000]测试C 语言版本几乎一瞬间跑完Python 版本也就几百毫秒。因此用数组打标记 双重循环的思路在这道题的约束下完全够用不必过度优化。5. 更进一步这题背后的思维模型5.1 “迭代函数 环检测”是一类通用套路这道题的内部结构其实是“给定一个函数 f反复迭代判断最终是进入某个终态还是进入循环”。如果把这个思路抽象出来它就是很多算法题里的“环检测”问题跟链表判环、图里找环、状态机死循环检测是同一套思维。有人看到 4 的迭代链 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4觉得这是数字游戏其实它就是一个典型的状态转移图。你从起点出发沿着有向边走要么走到出口 1要么走到一个环里出不来。我们只需要一个集合记录已访问过的状态就能判断归属。这个模式在很多题目里反复出现比如判断一个数是否是“快乐数”LeetCode 202就是一模一样的套路。你把这题吃透等于顺手把循环检测的模板也练了一遍。5.2 为什么“依附标记”要在主流程里顺手做从工程角度看这道题还教你一个设计技巧如果最终输出结果需要依赖多个维度自身属性 全局依赖关系不要把两个维度的计算完全拆开做否则要么重复遍历要么状态不同步。我在 3.1 的第一版代码里其实就犯了“状态混用”的错把appeared既当访问标记又当独立性存储。这种代码写起来快但后续读起来很痛苦而且容易引入隐性问题。后来拆成appear_flag、depend_flag、indep_val三个数组每个数组只承担一个职责逻辑瞬间清晰。这道题我个人最大的收获不是 AC 了而是养成了一个习惯遇到一个数要同时输出“自身计算值”和“被全局条件过滤”的时候先在纸上列出所有标记数组的名称和用途再动手写代码。5.3 Python 版本的对比参考如果你主攻 Python思路可以保持一致只是代码更简洁一些。我附一个参考写法供对比def square_sum(n): return sum(int(c) ** 2 for c in str(n)) def is_prime(n): if n 2: return False for i in range(2, int(n ** 0.5) 1): if n % i 0: return False return True A, B map(int, input().split()) depend set() indep {} happy_cache {} for i in range(A, B 1): seen set() num i steps 0 happy False while True: if num 1: happy True break if num in seen: break seen.add(num) num square_sum(num) steps 1 if happy: for x in seen: if A x B and x ! i: depend.add(x) indep[i] steps * 2 if is_prime(i) else steps found False for i in range(A, B 1): if i in indep and i not in depend: print(i, indep[i]) found True if not found: print(SAD)注意 Python 版本里depend用集合天然去重省得判断重复标记。哈希集合不会越界但性能比数组略低好在这题数据量不大完全没问题。这段代码能用但我仍建议你手敲一遍不要直接复制因为自己敲的过程中才会发现seen和depend交替顺序为什么会互相影响。6. 实战体验与经验沉淀做这道题的感觉很像在玩数字游戏的同时做了个小型工程先定义判断规则再定义标记策略最后统一输出三层逻辑环环相扣。我前后大概提交了四五轮才拿到全过前几轮都是栽在“依附关系的边界”和“素数翻倍”这两个细节上。反而核心的幸福数判定一次就写对了。如果你现在也卡在这题我建议按这个顺序排查第一步先确认is_prime判的是原始数第二步检查标记数组里是否排除“起点自己”第三步确认输出前所有标记都已经收集完毕而不是边算边打第四步用19 19、82 82、25 25这组本地数据跑一遍看看是不是符合预期。这套排查流程能覆盖我遇到过的全部常见问题。刷题刷到后期你会发现大部分丢分都不是因为算法不会而是这种“差一点就漏掉”的边界条件。把这题彻底吃透你以后遇到这类带依附关系的模拟题会从容很多。