Siêu palindrome trong C++

Số N gọi là siêu palindrome nếu N là palindrome và là bình phương của một palindrome. Cho L, R, đếm số siêu palindrome trong [L, R].

Ví dụ: L=5, R=500 → 3 (9, 121, 484).

Giải thuật

1. Sinh tất cả các palindrome x sao cho x² trong [L, R]. Giới hạn x ≤ sqrt(R) ≤ 10^9 (với R ≤ 10^18).
2. Sinh palindrome bằng đệ quy: bắt đầu từ 1 chữ số (0-9) và 2 chữ số (11*z). Mở rộng bằng cách chèn cặp chữ số两边.
3. Kiểm tra x² có phải palindrome không. Đếm những x thỏa mãn.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
class Solution {
    int ans = 0;
public:
    int superpalindromesInRange(string L, string R){
        long double lb = sqrtl(stol(L)), ub = sqrtl(stol(R));
        int M = log10l(ub) + 1;
        for (int z = 0; z <= 9; z++) {
            helper(z, 1, M, lb, ub);
            helper(11 * z, 2, M, lb, ub);
        }
        return ans;
    }
private:
    void helper(long x, int m, int M, long double lb, long double ub){
        if (x > ub) return;
        if (x >= lb && is_palindrome(x * x)) ans++;
        for (int i = 1; m + 2 * i <= M; i++) {
            long W = powl(10, m + 2 * i - 1) + 1;
            long w = powl(10, i);
            for (int z = 1; z <= 9; z++)
                helper(z * W + x * w, m + 2 * i, M, lb, ub);
        }
    }
    bool is_palindrome(long x){
        if (x == 0) return true;
        if (x % 10 == 0) return false;
        long left = x, right = 0;
        while (left >= right) {
            if (left == right || left / 10 == right) return true;
            right = 10 * right + (left % 10), left /= 10;
        }
        return false;
    }
};
int main(){
    Solution ob;
    cout << (ob.superpalindromesInRange("5", "500"));
}

Đầu vào

"5", "500"

Đầu ra

3