Codes/Volume 01/E0029 Distinct powers.cpp
// 1 < base and 1 < power considered
1 < base and 1 < power considered
1 < base and 1 < power considered
ll countDistinctPowers(int boundBase, int boundPower){
    vector<pair<int,int>> base = powerSieveTill(boundBase);
    unordered_set<int> powerProducts;
    int maxPower = 0;
    ll ans = 0;
    for(int num = boundBase; num > 1; num--){
        if(base[num].second > 1) continue;
        ll poweredNum = num, exponent = 0;
        while(poweredNum <= boundBase){
            exponent++;
            poweredNum *= num;
        }
        while(exponent > maxPower){
            maxPower++;
            for(int stdPower = 2; stdPower <= boundPower; stdPower++){
                int product = maxPower*stdPower;
                powerProducts.insert(product);
            }
        }
        ans += powerProducts.size();
    }
    return ans;
}
ll countDistinctPowers ( int boundBase , int boundPower ) { vector < pair < int , int > > base = powerSieveTill ( boundBase ) ; unordered_set < int > powerProducts ; int maxPower = 0 ; ll ans = 0 ; for ( int num = boundBase ; num > 1 ; num -- ) { if ( base [ num ] . second > 1 ) continue ; ll poweredNum = num , exponent = 0 ; while ( poweredNum <= boundBase ) { exponent ++ ; poweredNum *= num ; } while ( exponent > maxPower ) { maxPower ++ ; for ( int stdPower = 2 ; stdPower <= boundPower ; stdPower ++ ) { int product = maxPower * stdPower ; powerProducts . insert ( product ) ; } } ans += powerProducts . size ( ) ; } return ans ; }
1 < base and 1 < power considered
1 < base and 1 < power considered