丑陋的打表+前缀和二分。。。

#include <bits/stdc++.h>

using u32 = unsigned;
using i64 = long long;
using u64 = unsigned long long;
using u128 = unsigned __int128;

int S(i64 x) {
	int res = 0;
	while (x) {
		res += x % 10;
		x /= 10;
	}
	return res;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int L, R;
	std::cin >> L >> R;
	std::map<int, int> mp;
	for (i64 i = 1; i <= R; i++) {
		i64 p = i;
		int res = 0;
		while (p % 10 > 3) {
			res++;
			p /= 10;
			p++;
		}
		i = p * std::pow(10, res);
		if (S(i) * S(i) == S(i * i)) {
			mp[i]++;
		}
	}
	int res = 0;
	std::map<int, int> ans;
	std::vector<int> p;
	for (auto [x, y] : mp) {
		p.push_back(x);
		ans[x] = y + res;
		res += y;
	}

	auto l = lower_bound(p.begin(), p.end(), L) - p.begin() - 1;
	auto r = upper_bound(p.begin(), p.end(), R) - p.begin() - 1;

	std::cout << ans[p[r]] - ans[p[l]] << "\n";

	return 0;
}

我们先从简单情况入手,取一个两位数 $A=10X+Y$ . $X$ 为十位, $Y$ 为个位.

则 $S(A)*S(A)=(X+Y)^2 = X^2 + 2XY + Y^2$.

又 $A*A=(10X+Y)^2 = 100X^2 +20XY + Y^2$

比较两者系数.若 $A$ 为兔子数,则 $X^2$ 不能大于 $10$ ,否则会进位.

$XY$ 也不能大于 $10$ ,进位后得到的答案不一样.故可得 $X\le 3 ,Y\le 3$ .

以此类推,在此就不赘述了.三位数也可以通过这个方法推出来 $X\le 3 Y\le 3 Z\le 3$ .故我们猜想兔子数的每一位都小于等于 $3$ .

于是我们可以 $dfs$ +如上的剪枝.或者打表+二分.

又我们发现:如果当前的数不是兔子数,一定是当前最高位的问题.因为之前都可以,当前修改最高位不成了,一定是最高位的锅.于是就不搜了.continue掉.

#include<cstdio>
int L, R;
long long S(long long x) {
    int ans = 0;
    while (x > 0)
        ans += x%10, x /= 10;
    return ans;
}//计算数字的每一位之和 
int cal(int cur) {
    int ans = 0;
    for (int i=0; i<4; i++) {//定理:兔子数的每一位小于等于3 
        long long x = cur*10 + i;//扩大数字(即添加高位) 
        if (x == 0 || S(x*x) != S(x)*S(x))
            continue;//特判0 :因为题目要求正整数 
            //如果该数不符合要求,那么一定是当前位添加数的问题,即使高位再添加任何数都不行. 
        if (L <= x && x <= R)
            ans ++;//符合条件 
        if (x <= R/10)//还可以继续搜 
            ans += cal(x);
    }
    return ans;
}
int main() {
    scanf("%d%d",&L,&R);
    printf("%d",cal(0));//从0开始搜 
    return 0;
}