SRM484 Div1 Easy

250
解法が思いつかないので、小さい数を試す。
0, 1, 2, 3 以外の数字をどこかの桁に含む数は対象にならないらしい。
とりあえず、4進数にして順に試す。
0〜3なのは2乗して桁上がりが発生するとまずいから?

int S(lli n)
{
  int sum = 0;
  while (n) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

class RabbitNumber {
public:
  int theCount(int low, int high)
  {
    int ret = 0;
    for (int i = 0; i <= high; ++i) {
      string s;
      int n = i;
      while (n) {
        s += '0' + n % 4;
        n /= 4;
      }
      if (s.empty()) s += '0';
      reverse(s.begin(), s.end());
      lli m;
      sscanf(s.c_str(), "%lld", &m);
      if (m < (lli)low) continue;
      if ((lli)high < m) break;
      ret += S(m * m) == S(m) * S(m);
    }
    return ret;
  }

};