题目描述定义一个正整数s0s_0s0​的各位数字平方和为s1s_1s1​s1s_1s1​的各位数字平方和为s2s_2s2​依此类推。若存在某个i≥1i \ge 1i≥1使得si1s_i 1si​1则称原始整数s0s_0s0​为快乐数。例如从777开始得到序列7,49,97,130,10,17, 49, 97, 130, 10, 17,49,97,130,10,1因此777是快乐数。前几个快乐数为1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97,100,…1, 7, 10, 13, 19, 23, 28, 31, 32, 44, 49, 68, 70, 79, 82, 86, 91, 94, 97, 100, \ldots1,7,10,13,19,23,28,31,32,44,49,68,70,79,82,86,91,94,97,100,…它们到达111所需的迭代次数分别为1,6,2,3,5,4,4,3,4,5,5,3,…1, 6, 2, 3, 5, 4, 4, 3, 4, 5, 5, 3, \ldots1,6,2,3,5,4,4,3,4,5,5,3,…。非快乐数称为不快乐数其序列最终会进入不包含111的周期循环。快乐数的任意数字排列仍为快乐数快乐数乘以101010的任意幂仍为快乐数。输入格式输入包含nnn行每行对应一个测试用例。每行包含两个正整数LLL和HHH1≤L≤H≤999991 \le L \le H \le 999991≤L≤H≤99999分别表示闭区间的下界和上界。输出格式输出区间[L,H][L, H][L,H]内的所有快乐数及其到达111所需的迭代次数。每个快乐数占一行格式为快乐数后跟一个空格和迭代次数。相邻两个测试用例之间输出一个空行。样例输入5 28 233 250样例输出7 6 10 2 13 3 19 5 23 4 28 4 236 6 239 6题目分析本题要求在给定区间内找出所有快乐数并输出它们到达111所需的迭代次数。由于区间上界为999999999999999可以预先计算所有不超过该上界的数的快乐性质及迭代次数然后对每个查询直接筛选输出。快乐数的判定依赖于各位数字平方和的迭代过程。对于任意正整数nnn其各位数字平方和的最大值出现在999999999999999时为5×924055 \times 9^2 4055×92405。因此迭代过程中产生的所有后续值都不会超过405405405。这意味着可以预先计算111到405405405之间所有数的快乐性质然后利用这些结果快速判定更大的数。题目还指出快乐数的任意数字排列仍为快乐数且快乐数乘以101010的幂仍为快乐数。这些性质可以用于优化但直接预计算111到999999999999999的所有数也是可行的因为规模仅为10510^5105。解题思路采用动态规划与记忆化搜索相结合的方法。首先初始化数组happy和iterations其中happy[1] 1iterations[1] 1。对于每个数nnn通过迭代计算各位数字平方和同时记录已访问的数。若迭代过程中遇到已知的快乐数则当前数也是快乐数其迭代次数为已消耗步数加上已知快乐数的迭代次数若遇到已知的不快乐数或出现重复值则当前数及访问路径上的所有数均为不快乐数。预处理阶段遍历222到999999999999999的所有数对每个尚未确定性质的数调用检查函数。检查函数使用哈希集合记录当前路径上出现的数避免无限循环。当遇到快乐数时更新路径上所有数的性质与迭代次数当遇到不快乐数或重复值时将路径上所有数标记为不快乐。预处理完成后将所有快乐数按升序存入数组以便查询时快速筛选。对于每个查询区间[L,H][L, H][L,H]遍历快乐数数组输出落在区间内的快乐数及其迭代次数。注意相邻测试用例之间输出空行。代码实现// Happy Numbers// UVa ID: 944// Verdict: Accepted// Submission Date: 2017-03-08// UVa Run Time: 0.050s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintMAXN100000;intiterations[MAXN],happy[MAXN];voidcheck(intn){intoriginal,nextn,remainder;unordered_setintappeared;intelapsed0;while(true){if(happy[next]1){happy[n]1;iterations[n]iterations[next]elapsed;break;}elseif(happy[next]-1||appeared.find(next)!appeared.end()){for(autov:appeared)happy[v]-1;break;}appeared.insert(next);originalnext,next0;while(original0){remainderoriginal%10;nextremainder*remainder;original/10;}elapsed;}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);memset(happy,0,sizeof(happy));happy[1]1,iterations[1]1;for(inti2;iMAXN;i){if(happy[i]-1)continue;check(i);}intcounter0;for(inti1;iMAXN;i)if(happy[i]1)happy[counter]i;intcases0,L,H;while(cinLH){if(LH)swap(L,H);if(cases0)cout\n;for(inti0;icounter;i)if(happy[i]Lhappy[i]H)couthappy[i] iterations[happy[i]]\n;}return0;}总结本题的关键在于利用各位数字平方和的上界405405405以及快乐数性质的可传递性通过记忆化搜索预先计算所有数的快乐性质与迭代次数。预处理阶段的时间复杂度为O(MAXN×log⁡MAXN)O(MAXN \times \log MAXN)O(MAXN×logMAXN)空间复杂度为O(MAXN)O(MAXN)O(MAXN)。查询阶段直接遍历快乐数数组效率极高。需要注意迭代次数的定义从s0s_0s0​到111的步数且111本身的迭代次数为111。输出格式要求相邻测试用例之间有空行需妥善处理。