Encuentra un par (a, b) tal que Aa + Bb = N

Dados tres enteros N , A y B , la tarea es encontrar un par de enteros positivos (a, b) tales que A a + B b = N . Si no existe tal par, imprima -1 .

Ejemplos:

Entrada: N = 106, A = 3, B = 5 
Salida: 4 2
Explicación: El par (4, 2) satisface la respuesta, es decir, 3 4 +5 2 es igual a 106

Entrada: N = 60467200, A = 6, B = 4 
Salida: 10 5
Explicación: El par (10, 5) satisface la respuesta, es decir, 6 10 +4 5 es igual a 60467200

 

Enfoque: La idea es calcular log A N y log B N y verificar para cada par (i, j) (0 ≤ i ≤ log A N y 0 ≤ j ≤ log B N ), si A i + B j es igual a N o no. Siga los pasos a continuación para resolver el problema:

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate the minimum
// power of A and B greater than N
int power(long long int A, long long int N)
{
    // Stores the power of A which
    // is greater than N
    int count = 0;
    if (A == 1)
        return 0;
 
    while (N) {
 
        // Increment count by 1
        count++;
 
        // Divide N by A
        N /= A;
    }
    return count;
}
 
// Function to find a pair (a, b)
// such that A^a + B^b = N
void Pairs(long long int N, long long int A,
           long long int B)
{
    int powerA, powerB;
 
    // Calculate the minimum power
    // of A greater than N
    powerA = power(A, N);
 
    // Calculate the minimum power
    // of B greater than N
    powerB = power(B, N);
 
    // Make copy of A and B
    long long int intialB = B, intialA = A;
 
    // Traverse for every pair (i, j)
    A = 1;
    for (int i = 0; i <= powerA; i++) {
 
        B = 1;
        for (int j = 0; j <= powerB; j++) {
 
            // Check if B^j + A^i = N
            // To overcome the overflow problem
            // use B=N-A rather than B+A=N
            if (B == N - A) {
                cout << i << " " << j << endl;
                return;
            }
 
            // Increment power B by 1
            B *= intialB;
        }
 
        // Increment power A by 1
        A *= intialA;
    }
 
    // Finally print -1 if no pair
    // is found
    cout << -1 << endl;
    return;
}
 
// Driver Code
int main()
{
 
    // Given A, B and N
    long long int N = 106, A = 3, B = 5;
 
    // Function Call
    Pairs(N, A, B);
    return 0;
}

Java

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to calculate the minimum
// power of A and B greater than N
static int power(int A, int N)
{
     
    // Stores the power of A which
    // is greater than N
    int count = 0;
     
    if (A == 1)
        return 0;
 
    while (N > 0)
    {
         
        // Increment count by 1
        count++;
 
        // Divide N by A
        N /= A;
    }
    return count;
}
 
// Function to find a pair (a, b)
// such that A^a + B^b = N
static void Pairs(int N, int A, int B)
{
    int powerA, powerB;
 
    // Calculate the minimum power
    // of A greater than N
    powerA = power(A, N);
 
    // Calculate the minimum power
    // of B greater than N
    powerB = power(B, N);
 
    // Make copy of A and B
    int intialB = B, intialA = A;
 
    // Traverse for every pair (i, j)
    A = 1;
    for(int i = 0; i <= powerA; i++)
    {
         
        B = 1;
        for(int j = 0; j <= powerB; j++)
        {
             
            // Check if B^j + A^i = N
            // To overcome the overflow problem
            // use B=N-A rather than B+A=N
            if (B == N - A)
            {
                System.out.println(i + " " + j);
                return;
            }
 
            // Increment power B by 1
            B *= intialB;
        }
 
        // Increment power A by 1
        A *= intialA;
    }
 
    // Finally print -1 if no pair
    // is found
    System.out.println("-1");
    return;
}
 
// Driver Code
public static void main(String args[])
{
     
    // Given A, B and N
    int N = 106, A = 3, B = 5;
 
    // Function Call
    Pairs(N, A, B);
}
}
 
// This code is contributed by 18bhupenderyadav18

Python3

# Python program for the above approach
 
# Function to calculate the minimum
# power of A and B greater than N
def power(A, N):
   
    # Stores the power of A which
    # is greater than N
    count = 0;
    if (A == 1):
        return 0;
    while (N > 0):
       
        # Increment count by 1
        count += 1;
 
        # Divide N by A
        N //= A;
    return int(count);
 
# Function to find a pair (a, b)
# such that A^a + B^b = N
def Pairs(N, A, B):
    powerA, powerB = 0, 0;
 
    # Calculate the minimum power
    # of A greater than N
    powerA = power(A, N);
 
    # Calculate the minimum power
    # of B greater than N
    powerB = power(B, N);
 
    # Make copy of A and B
    intialB = B;
    intialA = A;
 
    # Traverse for every pair (i, j)
    A = 1;
    for i in range(powerA + 1):
        B = 1;
        for j in range(powerB + 1):
 
            # Check if B^j + A^i = N
            # To overcome the overflow problem
            # use B=N-A rather than B+A=N
            if (B == N - A):
                print(i , " " , j);
                return;
 
            # Increment power B by 1
            B *= intialB;
 
        # Increment power A by 1
        A *= intialA;
 
    # Finally pr-1 if no pair
    # is found
    print("-1");
    return;
 
# Driver Code
if __name__ == '__main__':
 
  # Given A, B and N
    N = 106;
    A = 3;
    B = 5;
 
    # Function Call
    Pairs(N, A, B);
 
# This code is contributed by 29AjayKumar

C#

// C# program for the above approach
using System;
 
class GFG
{
     
// Function to calculate the minimum
// power of A and B greater than N
static int power(int A, int N)
{
     
    // Stores the power of A which
    // is greater than N
    int count = 0;
     
    if (A == 1)
        return 0;
    while (N > 0)
    {
         
        // Increment count by 1
        count++;
 
        // Divide N by A
        N /= A;
    }
    return count;
}
 
// Function to find a pair (a, b)
// such that A^a + B^b = N
static void Pairs(int N, int A, int B)
{
    int powerA, powerB;
 
    // Calculate the minimum power
    // of A greater than N
    powerA = power(A, N);
 
    // Calculate the minimum power
    // of B greater than N
    powerB = power(B, N);
 
    // Make copy of A and B
    int intialB = B, intialA = A;
 
    // Traverse for every pair (i, j)
    A = 1;
    for(int i = 0; i <= powerA; i++)
    {
         
        B = 1;
        for(int j = 0; j <= powerB; j++)
        {
             
            // Check if B^j + A^i = N
            // To overcome the overflow problem
            // use B=N-A rather than B+A=N
            if (B == N - A)
            {
                Console.WriteLine(i + " " + j);
                return;
            }
 
            // Increment power B by 1
            B *= intialB;
        }
 
        // Increment power A by 1
        A *= intialA;
    }
 
    // Finally print -1 if no pair
    // is found
    Console.WriteLine("-1");
    return;
}
 
// Driver Code
public static void Main(String []args)
{
     
    // Given A, B and N
    int N = 106, A = 3, B = 5;
 
    // Function Call
    Pairs(N, A, B);
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// Javascript program for the above approach
 
// Function to calculate the minimum
// power of A and B greater than N
function power(A, N)
{
      
    // Stores the power of A which
    // is greater than N
    let count = 0;
      
    if (A == 1)
        return 0;
  
    while (N > 0)
    {
          
        // Increment count by 1
        count++;
  
        // Divide N by A
        N /= A;
    }
    return count;
}
  
// Function to find a pair (a, b)
// such that A^a + B^b = N
function Pairs(N, A, B)
{
    let powerA, powerB;
  
    // Calculate the minimum power
    // of A greater than N
    powerA = power(A, N);
  
    // Calculate the minimum power
    // of B greater than N
    powerB = power(B, N);
  
    // Make copy of A and B
    let letialB = B, letialA = A;
  
    // Traverse for every pair (i, j)
    A = 1;
    for(let i = 0; i <= powerA; i++)
    {
          
        B = 1;
        for(let j = 0; j <= powerB; j++)
        {
              
            // Check if B^j + A^i = N
            // To overcome the overflow problem
            // use B=N-A rather than B+A=N
            if (B == N - A)
            {
                document.write(i + " " + j);
                return;
            }
  
            // Increment power B by 1
            B *= letialB;
        }
  
        // Increment power A by 1
        A *= letialA;
    }
  
    // Finally print -1 if no pair
    // is found
    document.write("-1");
    return;
}
     
// driver function
 
    // Given A, B and N
    let N = 106, A = 3, B = 5;
  
    // Function Call
    Pairs(N, A, B);
     
    // This code is contributed by splevel62.
</script>   
Producción: 

4 2

 

Complejidad de tiempo: O((log A N)*(log B N))
Espacio auxiliar: O(1) 

Publicación traducida automáticamente

Artículo escrito por rj13to y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *