TopCoder SRM 350 Div1 Easy SumsOfPerfectPowers

問題

ある整数nが、2つのperfect powerの和であるとは、
1より大きな整数m,kおよび非負整数a,bが存在し、
n=a^m+b^kと書けることを言う。


lowerBound以上upperBound以下の整数のうち、
二つのperfect powerの和であるような整数の個数を求めよ。

制約条件

lowerBound,upperBound≦5000000

方針

エラトステネスの篩みたいに、
perfect powerを生成して、その数にフラグを立てていく。
全てのperfect powerを生成した後で、フラグの数を数える。

ソースコード

bool ok[5000001];

class SumsOfPerfectPowers {
	public:
	int howMany(int lowerBound, int upperBound) 
	{
		memset(ok,0,sizeof(ok));
		
		for(int a=0;a*a<=upperBound;a++){
			for(int b=0;a*a+b*b<=upperBound;b++){
				for(ll A=a*a;A<=upperBound;A*=a){
					for(ll B=b*b;A+B<=upperBound;B*=b){
						ok[A+B]=1;
						if(B<2)break;
					}
					if(A<2)break;
				}
			}
		}
		
		int ans=0;
		for(int i=lowerBound;i<=upperBound;i++)if(ok[i]){
			ans++;
		}
		return ans;
	}
};