TopCoder 練習

RabbitNumber(SRM 484 Div1 Easy)

■問題
S(x):=xの各桁の総和とする．S(x*x)=S(x)*S(x)となるxをRabbit Numberと呼ぶ．
low以上high以下の数の内，Rabbit Numberはいくつあるか．

■解法
chokudaiさんのニコ生を頼りに解く．
まず，小さい数について実験してみると，各桁は必ず3以下である事が分かる．これは，4*4=16から分かるように，4以上の数の次乗には繰り上がりが発生してしまうから．
よって，各桁が3以下である数について試せば良い．
入力の最大値は1,000,000,000であるが，上記の条件を満たすものは約260000個であり，候補が十分に絞れるので，あとは全探索すればよい．

public class RabbitNumber{
 public int theCount(int low, int high){
  int res=0;
  for(int i=1;;i++){
   long n=0;
   long r=1;
   for(int k=i;k!=0;k>>=2){
    n+=(k&3)*r;
    r*=10;
   }
   if(n<low)
    continue;
   if(n>high)
    break;
   if(S(n*n)==S(n)*S(n))
    res++;
  }
  return res;
 }

 long S(long x){
  long ret=0;
  for(;x!=0;x/=10)
   ret+=(x%10);
  return ret;
 }
}