Encuentra la suma de los números de 1 a n excluyendo aquellos que son potencias de K

Dados dos enteros N y K , la tarea es encontrar la suma de todos los números del rango [1, N] excluyendo aquellos que son potencias de K .
 

Ejemplos:

Entrada: N = 10, K = 3 
Salida: 42 
2 + 4 + 5 + 6 + 7 + 8 + 10 = 42 
Se excluyen 1, 3 y 9 por ser potencias de 3.
Entrada: N = 200, K = 30 
Salida: 20069  

Enfoque: Encuentra la suma de las siguientes series:  

1. pwrK: La suma de todas las potencias de K de [1, N], es decir , K ⁰ + K ¹ + K ² + … + K ^r tal que K ^r ≤ N
2. sumAll: la suma de todos los enteros del rango [1, N], es decir , (N * (N + 1)) / 2 .

El resultado será sumAll – pwrK
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
 
// Function to return the sum of all the
// powers of k from the range [1, n]
ll sumPowersK(ll n, ll k)
{
 
    // To store the sum of the series
    ll sum = 0, num = 1;
 
    // While current power of k <= n
    while (num <= n) {
 
        // Add current power to the sum
        sum += num;
 
        // Next power of k
        num *= k;
    }
 
    // Return the sum of the series
    return sum;
}
 
// Find to return the sum of the
// elements from the range [1, n]
// excluding those which are powers of k
ll getSum(ll n, ll k)
{
    // Sum of all the powers of k from [1, n]
    ll pwrK = sumPowersK(n, k);
 
    // Sum of all the elements from [1, n]
    ll sumAll = (n * (n + 1)) / 2;
 
    // Return the required sum
    return (sumAll - pwrK);
}
 
// Driver code
int main()
{
    ll n = 10, k = 3;
 
    cout << getSum(n, k);
 
    return 0;
}

// Java implementation of the approach
import java.io.*;
 
class GFG
{
 
// Function to return the sum of all the
// powers of k from the range [1, n]
static long sumPowersK(long n, long k)
{
 
    // To store the sum of the series
    long sum = 0, num = 1;
 
    // While current power of k <= n
    while (num <= n)
    {
 
        // Add current power to the sum
        sum += num;
 
        // Next power of k
        num *= k;
    }
 
    // Return the sum of the series
    return sum;
}
 
// Find to return the sum of the
// elements from the range [1, n]
// excluding those which are powers of k
static long getSum(long n, long k)
{
    // Sum of all the powers of k from [1, n]
    long pwrK = sumPowersK(n, k);
 
    // Sum of all the elements from [1, n]
    long sumAll = (n * (n + 1)) / 2;
 
    // Return the required sum
    return (sumAll - pwrK);
}
 
    // Driver code
    public static void main (String[] args)
    {
        long n = 10, k = 3;
        System.out.println( getSum(n, k));
 
    }
}
 
// This code is contributed by anuj_67..

# Python3 implementation of the approach
 
# Function to return the sum of all the
# powers of k from the range [1, n]
def sumPowersK(n, k) :
 
    # To store the sum of the series
    sum = 0; num = 1;
 
    # While current power of k <= n
    while (num <= n) :
 
        # Add current power to the sum
        sum += num;
 
        # Next power of k
        num *= k;
 
    # Return the sum of the series
    return sum;
     
 
# Find to return the sum of the
# elements from the range [1, n]
# excluding those which are powers of k
def getSum(n, k) :
 
    # Sum of all the powers of k from [1, n]
    pwrK = sumPowersK(n, k);
 
    # Sum of all the elements from [1, n]
    sumAll = (n * (n + 1)) / 2;
 
    # Return the required sum
    return (sumAll - pwrK);
 
 
# Driver code
if __name__ == "__main__" :
 
    n = 10; k = 3;
 
    print(getSum(n, k));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the sum of all the
// powers of k from the range [1, n]
static long sumPowersK(long n, long k)
{
 
    // To store the sum of the series
    long sum = 0, num = 1;
 
    // While current power of k <= n
    while (num <= n)
    {
 
        // Add current power to the sum
        sum += num;
 
        // Next power of k
        num *= k;
    }
 
    // Return the sum of the series
    return sum;
}
 
// Find to return the sum of the
// elements from the range [1, n]
// excluding those which are powers of k
static long getSum(long n, long k)
{
    // Sum of all the powers of k from [1, n]
    long pwrK = sumPowersK(n, k);
 
    // Sum of all the elements from [1, n]
    long sumAll = (n * (n + 1)) / 2;
 
    // Return the required sum
    return (sumAll - pwrK);
}
 
// Driver code
public static void Main ()
{
    long n = 10, k = 3;
    Console.WriteLine( getSum(n, k));
 
}
}
 
// This code is contributed by anuj_67..

<script>
// javascript implementation of the approach
 
    // Function to return the sum of all the
    // powers of k from the range [1, n]
    function sumPowersK(n , k) {
 
        // To store the sum of the series
        var sum = 0, num = 1;
 
        // While current power of k <= n
        while (num <= n) {
 
            // Add current power to the sum
            sum += num;
 
            // Next power of k
            num *= k;
        }
 
        // Return the sum of the series
        return sum;
    }
 
    // Find to return the sum of the
    // elements from the range [1, n]
    // excluding those which are powers of k
    function getSum(n , k) {
        // Sum of all the powers of k from [1, n]
        var pwrK = sumPowersK(n, k);
 
        // Sum of all the elements from [1, n]
        var sumAll = (n * (n + 1)) / 2;
 
        // Return the required sum
        return (sumAll - pwrK);
    }
 
    // Driver code
     
        var n = 10, k = 3;
        document.write(getSum(n, k));
 
 
// This code contributed by Rajput-Ji
</script>

42

Complejidad del tiempo: O(log _k N)

Espacio Auxiliar: O(1), ya que no se ha ocupado ningún espacio extra.