2010年11月20日土曜日

TopCoder 練習 SumsOfPerfectPowers(SRM 350 Div1 Easy)

SumsOfPerfectPowers(SRM 350 Div1 Easy)

■問題
本家参照.

■解法
chokudaiさんのニコ生を追従して解いた.指数は2以上なので,amまたはbkの候補を先に作っておく.あとは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;
}
}

0 件のコメント: