TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照．

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

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