Count of numbers in range [ L , R ] which can be represented as sum of two perfect powers | C ++ program for the above approach ; Function to find the number of numbers that can be expressed in the form of the sum of two perfect powers ; Stores all possible powers ; Push 1 and 0 in it ; Iterate over all the exponents ; Iterate over all possible numbers ; This loop will run for a maximum of sqrt ( R ) times ; Push this power in the array pows [ ] ; Increase the number ; Stores if i can be expressed as the sum of perfect power or not ; Iterate over all possible pairs of the array pows [ ] ; The number is valid ; Find the prefix sum of the array ok [ ] ; Return the count of required number ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int TotalPerfectPowerSum ( long long L , long long R ) { vector < long long > pows ; pows . push_back ( 0 ) ; pows . push_back ( 1 ) ; for ( int p = 2 ; p < 25 ; p ++ ) { long long int num = 2 ; while ( ( long long int ) ( pow ( num , p ) + 0.5 ) <= R ) { pows . push_back ( ( long long int ) ( pow ( num , p ) + 0.5 ) ) ; num ++ ; } } int ok [ R + 1 ] ; memset ( ok , 0 , sizeof ( ok ) ) ; for ( int i = 0 ; i < pows . size ( ) ; i ++ ) { for ( int j = 0 ; j < pows . size ( ) ; j ++ ) { if ( pows [ i ] + pows [ j ] <= R and pows [ i ] + pows [ j ] >= L ) { ok [ pows [ i ] + pows [ j ] ] = 1 ; } } } for ( int i = 0 ; i <= R ; i ++ ) { ok [ i ] += ok [ i - 1 ] ; } return ok [ R ] - ok [ L - 1 ] ; } signed main ( ) { int L = 5 , R = 8 ; cout << TotalPerfectPowerSum ( L , R ) ; return 0 ; }