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 106Entrada: 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:
- Primero, encuentre la potencia mínima de A y B que sea mayor que N y guárdela en las variables X e Y respectivamente.
- Compruebe cada par (i, j) tal que 0≤i≤X y 0≤j≤Y , y si A i + B j es igual a N , imprima el par (i, j) .
- Imprime -1 , si no se encuentra ese par.
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)