题目描述

如果一个正整数自身是回文数，而且它也是一个回文数的平方，那么我们称这个数为超级回文数。

现在，给定两个正整数 L 和 R （以字符串形式表示），返回包含在范围 [L, R] 中的超级回文数的数目。

样例

输入：L = "4", R = "1000"
输出：4
解释：
4，9，121，以及 484 是超级回文数。
注意 676 不是一个超级回文数： 26 * 26 = 676，但是 26 不是回文数。

注意

• 1 <= len(L) <= 18
• 1 <= len(R) <= 18
• L and R are strings representing integers in the range [1, 10^18).
• int(L) <= int(R)

算法

(枚举) $O(n^{\frac{1}{4}} \log n)$

1. 首先我们可以构造在 $10^9$ 内的回文数，然后将其平方后判定是否还是回文数。
2. 构造回文数只需要枚举一半数位的数字即可，本题中，枚举 1 至 n{\frac{1}{4}} 即可找到所有满足条件的回文数。
3. 对于枚举的每一个数字 $x$，有两种方式构造：$xx’$ 和 $xjx’$，分别判定即可。
4. 注意特判答案 1, 4, 9。

时间复杂度

• 枚举后只需要 $O(\log n)$ 的时间即可判定，故总时间复杂度为 $O(n^{\frac{1}{4}} \log n)$。

C++ 代码

class Solution {
public:
    #define LL long long
    bool check(string s) {
        for (int i = 0, j = s.length() - 1; i < j; i++, j--)
            if (s[i] != s[j])
                return false;
        return true;
    }
    int superpalindromesInRange(string L, string R) {
        LL l = stoll(L), r = stoll(R);
        int ans = 0;

        for (int j = 1; j <= 3; j++) {
            if (j * j >= l && j * j <= r)
                ans++;
        }

        for (int i = 1; i < 10000; i++) {
            string t = to_string(i);
            string rt = t;
            reverse(rt.begin(), rt.end());

            LL s = stoll(t + rt);
            s *= s;
            if (s > r)
                break;

            if (check(to_string(s)) && l <= s && s <= r)
                ans++;

            for (char j = '0'; j <= '9'; j++) {
                s = stoll(t + j + rt);
                s *= s;
                if (check(to_string(s)) && l <= s && s <= r)
                    ans++;
            }
        }
        return ans;
    }
};