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個であり，候補が十分に絞れるので，あとは全探索すればよい．

view plainprint?

1. public class RabbitNumber{  
2.  public int theCount(int low, int high){  
3.   int res=0;  
4.   for(int i=1;;i++){  
5.    long n=0;  
6.    long r=1;  
7.    for(int k=i;k!=0;k>>=2){  
8.     n+=(k&3)*r;  
9.     r*=10;  
10.    }  
11.    if(n<low)  
12.     continue;  
13.    if(n>high)  
14.     break;  
15.    if(S(n*n)==S(n)*S(n))  
16.     res++;  
17.   }  
18.   return res;  
19.  }  
20.   
21.  long S(long x){  
22.   long ret=0;  
23.   for(;x!=0;x/=10)  
24.    ret+=(x%10);  
25.   return ret;  
26.  }  
27. }  

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