这个题老是超时怎么办啊！想不到什么高效的方法了！

Question

Problem Description

给定一个正整数，然后将其每一位数字进行平方求和后形成下一个数，循环往复，直到生成的数在前面已经出现过为止，变换结束。
例如：给定44，2个4的平方求和变成32,3的平方加2的平方等于13，1的平方加3的平方等于10，然后就是1，下面仍然是1，序列变换结束。可简单描述成：44->32->13->10->1->1。
再例如给定2，其变换序列为:2->4->16->37->58->89->145->42->20->4。

我们规定，给定正整数n，若最后的变换终止于数值1，则称n为“快乐数”，否则就不是。

现在的任务：给定正整数N，请你计算区间[1..N]之间有多少个“快乐数”。

Input

测试数据有多组，首先输入测试的组数T （0<T<=20），然后是T组测试数据；每组测试输入一个正整数N(1 <= N <= 5,000,000).

Output

对于每组测试，请你计算区间[1..N]之间有多少个“快乐数”。

Sample Input
4
1
10
1000
10000
Sample Output
1
3
143
1442

Answer 1

我的想法是

建立一个布尔数组A，长度为502，若A【n】为真则表示n为快乐数。所以真正需要计算的只有502这个范围内，这个数组A可以提前计算出来，只需要循环502个数就可以

对于任意一个小于五百万的数a，计算它的“每一位的平方和”的值n，若A【n】为真则a为快乐数。有了数组A那么再判断每个数就只需要计算一次了。

计算数组A的时候也可以优化一下，一个数如果最后是快乐数，那么对它进行的每一步“求每位平方和”的值都是快乐数。