PTA上有这么一道题，名字起得特别文艺，叫“特立独行的幸福”。我一开始以为是什么情感鸡汤题，点进去才发现是实打实的数论模拟题，很多人在“幸福数”“依附关系”“独立性”这几个概念上绕得头晕。尤其是“依附”这两个字，题目说得很抽象，代码上处理起来就更抽象，不少同学第一次AC失败都是卡在“这个数到底算不算特立独行”的判断上。
如果你正在刷PTA题库、备战天梯赛，或者刚学到数组和集合的应用这块，这道题很适合拿来练手。它不考什么高深算法，却能帮你想清楚一件事：当一个数的求解过程会牵动其他数时，你怎么在编程里设计标记和去重。本文不打算光贴一份能过的代码，我会把题目从数学定义拆到代码设计，把每个容易踩的坑都翻出来讲一遍，顺便分享我当时调试时排掉的一个隐雷，希望能帮你真正吃透这道题。
1. 先把题目的规则彻底读懂
1.1 “幸福数”的迭代定义
题目里说的幸福数，是指把一个十进制整数的各位数字分别平方后再求和，得到一个新数，然后重复这个过程。如果最终能变成 1，那这个数就是幸福数。比如 19：
- 19 拆位 1 和 9，平方和是 1 + 81 = 82
- 82 拆位 8 和 2，平方和是 64 + 4 = 68
- 68 拆位 6 和 8，平方和是 36 + 64 = 100
- 100 拆位 1、0、0，平方和是 1
所以 19 会经过 82 → 68 → 100 → 1，最终收敛到 1，19 是幸福数。
但有些数永远别想变成 1，它们会掉进一个循环里面。比如 4：
- 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
绕了一圈又回到 4，这样就是非幸福数。我当年第一次写这道题的时候，以为一个数迭代几次还不到 1 就能判死，结果错得离谱。判断非幸福数的唯一标准不是“迭代次数够不够多”，而是“是否出现了重复的数字”。一旦重复，就说明进入循环，再迭代一万遍也白搭。
1.2 “特立独行”和“依附关系”
光会判断幸福数还不够，题目还要求“特立独行”。怎么定义特立独行？一个幸福数如果出现在其他幸福数的迭代过程中，它就不是特立独行的。
举个例子，假设区间里面同时有 19 和 82，19 的迭代过程是 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。
但这里有个隐藏规则：如果这个幸福数本身是素数，那么它的独立性要翻倍。注意，是原始的那个数，不是迭代过程中间产生的数。比如区间里有 19，19 是素数，那独立性就要输出 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 3（82 是幸福数，迭代链 82 → 68 → 100 → 1 共 3 次，82 不是素数，独立性为 3），但如果错加k == i的条件，输出就会变成 SAD。这个 case 特别适合用来检测你的依附标记逻辑是否写对了。
3.3 区间内自变量与中间变量互不干扰的关键点
还有一个小细节值得单独拎出来说：一个数可能是别人链上的中间数，同时它自己的独立性也存在。你不能因为它在别人的链上出现过就直接把它的indep_val抹掉，正确的做法是保留它的独立性，只在最终输出的时候用depend_flag过滤掉。
有人问为什么不直接在判断幸福数时跳过那些depend_flag的数字，因为这样会出逻辑漏洞：假设 i 是区间内第一个数，它的迭代链经过 j，j 在区间内。那么处理 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 1，1 是幸福数，迭代链 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 3，82 不是素数。 - 输入
25 25，25 → 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这组本地数据跑一遍，看看是不是符合预期。这套排查流程能覆盖我遇到过的全部常见问题。刷题刷到后期你会发现，大部分丢分都不是因为算法不会，而是这种“差一点就漏掉”的边界条件。把这题彻底吃透，你以后遇到这类带依附关系的模拟题，会从容很多。
