mayoko’s diary

プロコンとかいろいろ。

SRM 484 div1 easy:RabbitNumber

解法

二乗した数はたかだか 18 桁で, 各数字は 最大 9 なので, 数字の和は 162 以下です。
なので, 二乗する前の数字の各桁の和は 12 以下でないとダメです。ということで, 桁の和が 12 より大きくなったら枝刈りするように探索したら通りました。

ll p10[11];
int ans;

void dfs(int keta, ll now, int sum, const int limit) {
    if (keta == 0) {
        for (int i = 0; i < 10; i++) {
            ll tmp = now+i;
            if (tmp > limit) break;
            ll mul = tmp*tmp;
            int sum0 = 0, sum1 = 0;
            while (tmp) {
                sum0 += tmp%10;
                tmp /= 10;
            }
            while (mul) {
                sum1 += mul%10;
                mul /= 10;
            }
            if (sum1 == sum0*sum0) ans++;
        }
        return;
    }
    for (int i = 0; i < 10; i++) {
        if (sum+i > 12) break;
        if (now+p10[keta]*i > limit) break;
        dfs(keta-1, now+p10[keta]*i, sum+i, limit);
    }
}

class RabbitNumber {
public:
    int theCount(int low, int high) {
        p10[0] = 1;
        for (int i = 1; i <= 10; i++) p10[i] = p10[i-1]*10;
        ans = 0;
        dfs(9, 0, 0, high);
        int ret = ans;
        ans = 0;
        dfs(9, 0, 0, low-1);
        ret -= ans;
        return ret;
    }
};