TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照．

■解法
chokudaiさんのニコ生を追従して解いた．指数は2以上なので，a^mまたはb^kの候補を先に作っておく．あとは2重ループで条件を満たす数のフラグを立てるだけ．

view plainprint?

1. import java.util.*;  
2.   
3. public class SumsOfPerfectPowers{  
4.  public int howMany(int lowerBound, int upperBound){  
5.   boolean[] dp=new boolean[upperBound+1];  
6.   TreeSet<Integer> set=new TreeSet<Integer>();  
7.   set.add(0);  
8.   set.add(1);  
9.   for(int a=2;a*a<=upperBound;a++){  
10.    for(long r=a*a;r<=upperBound;r*=a){  
11.     set.add((int)r);  
12.    }  
13.   }  
14.   for(int a:set){  
15.    for(int b:set){  
16.     if(a+b<=upperBound){  
17.      dp[a+b]=true;  
18.     }  
19.    }  
20.   }  
21.   int ret=0;  
22.   for(int i=lowerBound;i<=upperBound;i++){  
23.    if(dp[i]){  
24.     ret++;  
25.    }  
26.   }  
27.   return ret;  
28.  }  
29. }  

import java.util.*;

public class SumsOfPerfectPowers{
 public int howMany(int lowerBound, int upperBound){
  boolean[] dp=new boolean[upperBound+1];
  TreeSet<Integer> set=new TreeSet<Integer>();
  set.add(0);
  set.add(1);
  for(int a=2;a*a<=upperBound;a++){
   for(long r=a*a;r<=upperBound;r*=a){
    set.add((int)r);
   }
  }
  for(int a:set){
   for(int b:set){
    if(a+b<=upperBound){
     dp[a+b]=true;
    }
   }
  }
  int ret=0;
  for(int i=lowerBound;i<=upperBound;i++){
   if(dp[i]){
    ret++;
   }
  }
  return ret;
 }
}