qq_33070397 2015-11-30 12:22 采纳率: 62.5%
浏览 1611
已采纳

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

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图片说明

  • 写回答

3条回答 默认 最新

  • 木艮氵 2015-12-01 10:52
    关注

    我的想法是

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

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

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

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥20 wireshark抓不到vlan
  • ¥20 关于#stm32#的问题:需要指导自动酸碱滴定仪的原理图程序代码及仿真
  • ¥20 设计一款异域新娘的视频相亲软件需要哪些技术支持
  • ¥15 stata安慰剂检验作图但是真实值不出现在图上
  • ¥15 c程序不知道为什么得不到结果
  • ¥40 复杂的限制性的商函数处理
  • ¥15 程序不包含适用于入口点的静态Main方法
  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来