题解

#include <vector>
#include <algorithm>
#include <cstdint>
#include <iostream>

bool is_rabbit_number(uint64_t n) {
    auto sum_digits = [](uint64_t x) -> int {
        int sum = 0;
        while (x > 0) {
            sum += x % 10;
            x /= 10;
        }
        return sum;
    };
    int s = sum_digits(n);
    uint64_t sq = n * n;
    int sum_sq = sum_digits(sq);
    return sum_sq == s * s;
}

void dfs(int pos, int sum, uint64_t num, std::vector<uint64_t>& candidates, uint64_t max_n = 1000000000ULL) {
    if (pos == -1) {
        if (num <= max_n) {
            candidates.push_back(num);
        }
        return;
    }
    for (int d = 0; d <= 9; ++d) {
        if (sum + d > 13) break;
        uint64_t new_num = num * 10ULL + static_cast<uint64_t>(d);
        if (new_num > max_n) continue;
        dfs(pos - 1, sum + d, new_num, candidates, max_n);
    }
}

int count_rabbit_numbers(uint64_t L, uint64_t R) {
    static std::vector<uint64_t> rabbits;
    static bool initialized = false;
    if (!initialized) {
        std::vector<uint64_t> candidates;
        dfs(9, 0, 0ULL, candidates);
        for (auto x : candidates) {
            if (is_rabbit_number(x)) {
                rabbits.push_back(x);
            }
        }
        std::sort(rabbits.begin(), rabbits.end());
        initialized = true;
    }
    auto it1 = std::lower_bound(rabbits.begin(), rabbits.end(), L);
    auto it2 = std::upper_bound(it1, rabbits.end(), R);
    return static_cast<int>(it2 - it1);
}

int main(){
    int l,r;
    std::cin>>l>>r;
    std::cout<<count_rabbit_numbers(l,r)<<std::endl;
    return 0;
}