V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
zeninger
V2EX  ›  问与答

求 10 的 100 次方内的 happy number 的个数,大家有什么好的思路?

  •  
  •   zeninger · 2021-03-01 17:06:20 +08:00 · 1250 次点击
    这是一个创建于 1365 天前的主题,其中的信息可能已经有所发展或是发生改变。

    前段时间刷到力扣 202 题:欢乐数,虽然是一道简单题,但是题目和解题思路都非常有意思。

    闲来无事在网上搜索一下类似的题目,发现在 hackerank 有一道类似的题目,要求 10^k 以内的非欢乐数的个数,k 最大可以到 200.

    这个数据规模用力扣 202 题中思路应该是解决不了的,大家有什么好的思路?

    2 条回复    2021-03-02 15:39:43 +08:00
    LRvx
        1
    LRvx  
       2021-03-01 20:40:15 +08:00
    有人给了一个很好的数位 dp 解法: https://euler.stephan-brumme.com/92/
    metaquant
        2
    metaquant  
       2021-03-02 15:39:43 +08:00
    设 f(n,k)表示 10^k 以内的数字其各位数平方之和等于 n 的个数, 则有:

    ![]( https://images-1252829441.cos.ap-guangzhou.myqcloud.com/img/20210302153707.png)

    对于 10^k 以内的数字,其最大平方和为 81k,则只需要求出 81k 以内的快乐数,对每个快乐数,使用 f(n,k )计算 k 位数内平方和等于 n 的个数,再加总,就是题目中要求的。

    更详细的分析参见: https://pe.metaquant.org/pe092.html
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2776 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 15:15 · PVG 23:15 · LAX 07:15 · JFK 10:15
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.