c++ - 快速找到不开心号码的方法

Question

我正在尝试解决一个问题。给定一个整数范围，用户必须找出给定范围内不开心的人数。

Unhappy number - 一个数字 n，使得从 n 开始迭代这个数字平方和映射永远不会达到数字 1。

我尝试使用蛮力方法计算数字的平方和，如果在任何时刻它等于其中任何一个 (4, 16, 37, 58, 89, 145, 42, 20)那么这是一个不快乐的数字。

这种方法就是给TLE有没有更好的方法？？

范围在 1 到 10^18 之间。

Answer 1

您的范围在 1 到 10¹⁸ 之间。这意味着您的号码最多包含 18 位数字。

考虑一个数字的最大平方是 9² = 81，在进行平方数字和一次最大数字是 18 * 81 = 1458 之后。

所以一个平方数字和加上一个约 1500 个元素的查找表就足够了。

或者两个平方数字和加上一个约 330 个元素的查找表:

static const bool unhappy[330] {
    1,0,1,1,1,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,1,1,
    1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,
    1,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,1,1,0,1,1,0,1,1,0,1,1,0,1,1,1,1,1,0,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,
    0,1,0,0,1,1,1,1,1,1,1,1,1,0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,0,1,
    1,1,0,1,1,1,1,1,0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0,1,1,
    1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1,1,1,0,0,1,
    1,1,1,1,1,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0,1,1,0
}

inline bool is_unhappy(uint64_t n) {
    while (n >= 330) {
        int r = 0;
        while (n > 0) {
            int d = n % 10;
            r += d*d;
            n /= 10;
        }
        n = r;
    }

    return unhappy[n];
}