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