题解 P1362 【兔子数】

· · 题解

看完下面的两篇题解,我总觉得有些敷衍.只是给出结论,没有证明.估计怎么证明自己也不清楚.只是打表找规律.

我来粗略地证明一下:

证明:

我们先从简单情况入手,取一个两位数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<=3 ,Y<=3.

以此类推,在此就不赘述了.我自己推了一下,三位数也可以通过这个方法推出来X<=3 Y<=3 Z<=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;
}