企业官网建设流程全解析

题目描述

定义一个正整数s0s_0s0​的各位数字平方和为s1s_1s1​，s1s_1s1​的各位数字平方和为s2s_2s2​，依此类推。若存在某个i≥1i \ge 1i≥1使得si=1s_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和HHH（1≤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×92=4055 \times 9^2 = 4055×92=405。因此，迭代过程中产生的所有后续值都不会超过405405405。这意味着可以预先计算111到405405405之间所有数的快乐性质，然后利用这些结果快速判定更大的数。

题目还指出，快乐数的任意数字排列仍为快乐数，且快乐数乘以101010的幂仍为快乐数。这些性质可以用于优化，但直接预计算111到999999999999999的所有数也是可行的，因为规模仅为10510^5105。

解题思路

采用动态规划与记忆化搜索相结合的方法。首先初始化数组happy和iterations，其中happy[1] = 1，iterations[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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=100000;intiterations[MAXN],happy[MAXN];voidcheck(intn){intoriginal,next=n,remainder;unordered_set<int>appeared;intelapsed=0;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);original=next,next=0;while(original>0){remainder=original%10;next+=remainder*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(inti=2;i<MAXN;i++){if(happy[i]==-1)continue;check(i);}intcounter=0;for(inti=1;i<MAXN;i++)if(happy[i]==1)happy[counter++]=i;intcases=0,L,H;while(cin>>L>>H){if(L>H)swap(L,H);if(cases++>0)cout<<'\n';for(inti=0;i<counter;i++)if(happy[i]>=L&&happy[i]<=H)cout<<happy[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。输出格式要求相邻测试用例之间有空行，需妥善处理。