Encuentre el número de soluciones para la ecuación dada

Dados tres enteros A , B y C , la tarea es encontrar el conteo de valores de X tal que se cumpla la siguiente condición, 
X = B * Sm(X) ^A + C donde Sm(X) denota la suma de dígitos de X y 1 < X < 10 ⁹ .
Ejemplos: 
 

Entrada: A = 3, B = 2, C = 8 
Salida: 3 
Para X = 10 , 2 * (1) ³ + 8 = 10 
Para X = 2008 , 2 * (10) ³ + 8 = 2008 
Para X = 13726 , 2 * (19) ³ + 8 = 13726
Entrada: A = 2, B = 3, C = 10 
Salida: 1 
 

Enfoque: Aquí se puede hacer una observación importante de que la suma de dígitos puede ser como máximo 81 (es decir, X = 999999999) y correspondiente a cada suma de dígitos, obtenemos un único valor de X. Entonces podemos iterar a través de cada suma de dígitos y verificar si el valor resultante de X es válido o no.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of
// valid values of X
int getCount(int a, int b, int c)
{
    int count = 0;
 
    // Iterate through all possible
    // sum of digits of X
    for (int i = 1; i <= 81; i++) {
 
        // Get current value of X for sum of digits i
        int cr = b * pow(i, a) + c;
 
        int tmp = cr;
        int sm = 0;
 
        // Find sum of digits of cr
        while (tmp) {
            sm += tmp % 10;
            tmp /= 10;
        }
 
        // If cr is a valid choice for X
        if (sm == i && cr < 1e9)
            count++;
    }
 
    // Return the count
    return count;
}
 
// Driver code
int main()
{
    int a = 3, b = 2, c = 8;
    cout << getCount(a, b, c);
 
    return 0;
}

// Java implementation of the approach
class GfG
{
 
// Function to return the count of
// valid values of X
static int getCount(int a, int b, int c)
{
    int count = 0;
 
    // Iterate through all possible
    // sum of digits of X
    for (int i = 1; i <= 81; i++)
    {
 
        // Get current value of X for sum of digits i
        int cr = b * (int)Math.pow(i, a) + c;
 
        int tmp = cr;
        int sm = 0;
 
        // Find sum of digits of cr
        while (tmp != 0)
        {
            sm += tmp % 10;
            tmp /= 10;
        }
 
        // If cr is a valid choice for X
        if (sm == i && cr < 1e9)
            count++;
    }
 
    // Return the count
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int a = 3, b = 2, c = 8;
    System.out.println(getCount(a, b, c));
}
}
 
// This code is contributed by Prerna Saini.

# Python3 implementation of the approach
 
# Function to return the count of
# valid values of X
def getCount(a, b, c):
 
    count = 0
 
    # Iterate through all possible
    # sum of digits of X
    for i in range(1, 82):
 
        # Get current value of X for
        # sum of digits i
        cr = b * pow(i, a) + c
 
        tmp = cr
        sm = 0
 
        # Find sum of digits of cr
        while (tmp):
            sm += tmp % 10
            tmp //= 10
         
        # If cr is a valid choice for X
        if (sm == i and cr < 10**9):
            count += 1
     
    # Return the count
    return count
 
# Driver code
a, b, c = 3, 2, 8
print(getCount(a, b, c))
 
# This code is contributed by Mohit Kumar

// C# implementation of the approach
using System;
 
class GFG
{
 
// Function to return the count of
// valid values of X
static int getCount(int a, int b, int c)
{
    int count = 0;
 
    // Iterate through all possible
    // sum of digits of X
    for (int i = 1; i <= 81; i++)
    {
 
        // Get current value of X for sum
        // of digits i
        int cr = b * (int)Math.Pow(i, a) + c;
 
        int tmp = cr;
        int sm = 0;
 
        // Find sum of digits of cr
        while (tmp != 0)
        {
            sm += tmp % 10;
            tmp /= 10;
        }
 
        // If cr is a valid choice for X
        if (sm == i && cr < 1e9)
            count++;
    }
 
    // Return the count
    return count;
}
 
// Driver code
public static void Main()
{
    int a = 3, b = 2, c = 8;
    Console.Write(getCount(a, b, c));
}
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP implementation of the approach
 
// Function to return the count of
// valid values of X
function getCount($a, $b, $c)
{
    $count = 0;
 
    // Iterate through all possible
    // sum of digits of X
    for ($i = 1; $i <= 81; $i++)
    {
 
        // Get current value of X for sum of digits i
        $cr = $b * (int)pow($i, $a) + $c;
 
        $tmp = $cr;
        $sm = 0;
 
        // Find sum of digits of cr
        while ($tmp != 0)
        {
            $sm += $tmp % 10;
            $tmp /= 10;
        }
 
        // If cr is a valid choice for X
        if ($sm == $i && $cr < 1e9)
            $count++;
    }
 
    // Return the count
    return $count;
}
 
// Driver code
{
    $a = 3; $b = 2;$c = 8;
    echo(getCount($a, $b, $c));
}
 
// This code is contributed by Code_Mech.

<script>
 
// Javascript implementation of the above approach
 
// Function to return the count of
// valid values of X
function getCount(a, b, c)
{
    let count = 0;
 
    // Iterate through all possible
    // sum of digits of X
    for (let i = 1; i <= 81; i++)
    {
 
        // Get current value of X for sum of digits i
        let cr = b * Math.pow(i, a) + c;
 
        let tmp = cr;
        let sm = 0;
 
        // Find sum of digits of cr
        while (tmp != 0)
        {
            sm += tmp % 10;
            tmp = Math.floor(tmp / 10);
        }
 
        // If cr is a valid choice for X
        if (sm == i && cr < 1e9)
            count++;
    }
 
    // Return the count
    return count;
}
 
// driver program
     
    let a = 3, b = 2, c = 8;
    document.write(getCount(a, b, c));
   
</script>

3

Complejidad temporal : O(k*d) donde k = 81 y d es el número de dígitos de X para cada valor correspondiente de k. 
Espacio Auxiliar : O(1), ya que no se ha tomado ningún espacio extra.