SumsOfPerfectPowers
SRM 350 · 2007-05-23 · by Xixas
SRM 350 · 2007-05-23 · by Xixas · Simple Math, Simple Search, Iteration
Problem Statement
Problem Statement
A non-negative integer n is said to be a sum of two perfect powers if there exist two non-negative integers a and b such that am + bk = n for some positive integers m and k, both greater than 1. Given two non-negative integers lowerBound and upperBound, return the number of integers between lowerBound and upperBound, inclusive, that are sums of two perfect powers.
Constraints
- lowerBound will be between 0 and 5000000, inclusive.
- upperBound will be between lowerBound and 5000000, inclusive.
Examples
0)
0 1 Returns: 2
0 and 1 are both sums of two perfect powers since 0 = 0 + 0 and 1 = 12 + 02.
1)
5 6 Returns: 1
5 is a sum of two perfect powers since 5 = 22 + 12 while 6 is not.
2)
25 30 Returns: 5
Only 30 is not a sum of two perfect powers.
3)
103 103 Returns: 0
There may be no desired integers in the range.
4)
1 100000 Returns: 33604
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class SumsOfPerfectPowers with a public method int howMany(int lowerBound, int upperBound) · 86 test cases · 2 s / 256 MB per case