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; } };