Count numbers in a range having GCD of powers of prime factors equal to 1 | C ++ implementation of the approach ; Vector to store powers greater than 3 ; Set to store perfect squares ; Set to store powers other than perfect squares ; Pushing squares ; if the values is already a perfect square means present in the set ; Run loop until some power of current number doesn 't exceed MAX ; Pushing only odd powers as even power of a number can always be expressed as a perfect square which is already present in set squares ; Inserting those sorted values of set into a vector ; Precompute the powers ; Calculate perfect squares in range using sqrtl function ; Calculate upper value of R in vector using binary search ; Calculate lower value of L in vector using binary search ; Calculate perfect powers ; Compute final answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  1000005 NEW_LINE #define MAX  1e18 NEW_LINE vector < long int > powers ; set < long int > squares ; set < long int > s ; void powersPrecomputation ( ) { for ( long int i = 2 ; i < N ; i ++ ) { squares . insert ( i * i ) ; if ( squares . find ( i ) != squares . end ( ) ) continue ; long int temp = i ; while ( i * i <= MAX / temp ) { temp *= ( i * i ) ; s . insert ( temp ) ; } } for ( auto x : s ) powers . push_back ( x ) ; } long int calculateAnswer ( long int L , long int R ) { powersPrecomputation ( ) ; long int perfectSquares = floor ( sqrtl ( R ) ) - floor ( sqrtl ( L - 1 ) ) ; long int high = upper_bound ( powers . begin ( ) , powers . end ( ) , R ) - powers . begin ( ) ; long int low = lower_bound ( powers . begin ( ) , powers . end ( ) , L ) - powers . begin ( ) ; long perfectPowers = perfectSquares + ( high - low ) ; long ans = ( R - L + 1 ) - perfectPowers ; return ans ; } int main ( ) { long int L = 13 , R = 20 ; cout << calculateAnswer ( L , R ) ; return 0 ; }