Dado un rango [L, R] , la tarea es encontrar la cantidad de números en el rango [L, R] que se pueden expresar como una suma de dos potencias perfectas.
Ejemplos:
Entrada: L = 0, R = 1
Salida: 2
Explicación:
Los números válidos son:
- 1 como se puede expresar como, 1 = 1 2 + 0 2 .
- 0 como se puede expresar como, 0 = 0 2 + 0 2 .
Por lo tanto, la cuenta de tales números es 2.
Entrada: L = 5, R = 8
Salida: 2
Explicación:
Los números válidos son:
- 5 como se puede expresar como, 5 = 1 2 + 2 2 .
- 8 como se puede expresar como, 0 = 0 2 + 2 3 .
Por lo tanto, la cuenta de tales números es 2.
Enfoque: El problema dado se puede resolver usando algunas observaciones matemáticas . Siga los pasos a continuación para resolver el problema:
- Genere toda la potencia posible de todos los números que son menores que R a partir de 2 y almacene esos números en una array pow[] .
- Inicialice una array booleana , digamos arr[] de tamaño (R + 1) como 0 .
- Genere todos los pares distintos posibles de la array pow[] y, si la suma de los pares es como máximo R , márquela como 1 en la array arr[] .
- Ahora, encuentre la suma del prefijo de la array arr[] .
- Después de completar los pasos anteriores, imprima el valor de arr[R] – arr[L – 1] como resultado.
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 find the number of numbers
// that can be expressed in the form of
// the sum of two perfect powers
int TotalPerfectPowerSum(long long L,
long long R)
{
// Stores all possible powers
vector<long long> pows;
// Push 1 and 0 in it
pows.push_back(0);
pows.push_back(1);
// Iterate over all the exponents
for (int p = 2; p < 25; p++) {
// Iterate over all possible numbers
long long int num = 2;
// This loop will run for a
// maximum of sqrt(R) times
while ((long long int)(pow(num, p) + 0.5) <= R) {
// Push this power in
// the array pows[]
pows.push_back(
(long long int)(pow(num, p) + 0.5));
// Increase the number
num++;
}
}
// Stores if i can be expressed as
// the sum of perfect power or not
int ok[R + 1];
memset(ok, 0, sizeof(ok));
// Iterate over all possible pairs
// of the array pows[]
for (int i = 0;
i < pows.size(); i++) {
for (int j = 0;
j < pows.size(); j++) {
if (pows[i] + pows[j] <= R
and pows[i] + pows[j] >= L) {
// The number is valid
ok[pows[i] + pows[j]] = 1;
}
}
}
// Find the prefix sum of the
// array ok[]
for (int i = 0; i <= R; i++) {
ok[i] += ok[i - 1];
}
// Return the count of required number
return ok[R] - ok[L - 1];
}
// Driver Code
signed main()
{
int L = 5, R = 8;
cout << TotalPerfectPowerSum(L, R);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG {
// Function to find the number of numbers
// that can be expressed in the form of
// the sum of two perfect powers
static int TotalPerfectPowerSum(int L, int R)
{
// Stores all possible powers
ArrayList<Integer> pows = new ArrayList<Integer>();
// Push 1 and 0 in it
pows.add(0);
pows.add(1);
// Iterate over all the exponents
for (int p = 2; p < 25; p++) {
// Iterate over all possible numbers
int num = 2;
// This loop will run for a
// maximum of sqrt(R) times
while ((int)(Math.pow(num, p) + 0.5) <= R) {
// Push this power in
// the array pows[]
pows.add((int)(Math.pow(num, p) + 0.5));
// Increase the number
num++;
}
}
// Stores if i can be expressed as
// the sum of perfect power or not
int[] ok = new int[R + 2];
// memset(ok, 0, sizeof(ok));
// Iterate over all possible pairs
// of the array pows[]
for (int i = 0; i < pows.size(); i++) {
for (int j = 0; j < pows.size(); j++) {
if (pows.get(i) + pows.get(j) <= R
&& pows.get(i) + pows.get(j) >= L) {
// The number is valid
ok[pows.get(i) + pows.get(j)] = 1;
}
}
}
// Find the prefix sum of the
// array ok[]
for (int i = 1; i <= R; i++) {
ok[i] += ok[i - 1];
}
// Return the count of required number
return ok[R] - ok[L - 1];
}
// Driver Code
public static void main(String args[])
{
int L = 5, R = 8;
System.out.print(TotalPerfectPowerSum(L, R));
}
}
// This code is contributed by avijitmondal1998.
Python3
# python program for the above approach # Function to find the number of numbers # that can be expressed in the form of # the sum of two perfect powers def TotalPerfectPowerSum(L, R): # Stores all possible powers pows = [] # Push 1 and 0 in it pows.append(0) pows.append(1) # Iterate over all the exponents for p in range(2, 25): # Iterate over all possible numbers num = 2 # This loop will run for a # maximum of sqrt(R) times while ((int)(pow(num, p) + 0.5) <= R): # Push this power in # the array pows[] pows.append((int)(pow(num, p) + 0.5)) # Increase the number num = num + 1 # Stores if i can be expressed as # the sum of perfect power or not ok = [0 for _ in range(R + 1)] # int ok[R + 1]; # memset(ok, 0, sizeof(ok)); # Iterate over all possible pairs # of the array pows[] for i in range(0, int(len(pows))): for j in range(0, len(pows)): if (pows[i] + pows[j] <= R and pows[i] + pows[j] >= L): # The number is valid ok[pows[i] + pows[j]] = 1 # Find the prefix sum of the # array ok[] for i in range(0, R+1): ok[i] += ok[i - 1] # Return the count of required number return ok[R] - ok[L - 1] # Driver Code if __name__ == "__main__": L = 5 R = 8 print(TotalPerfectPowerSum(L, R)) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to find the number of numbers
// that can be expressed in the form of
// the sum of two perfect powers
static int TotalPerfectPowerSum(long L, long R)
{
// Stores all possible powers
List<long> pows = new List<long>();
// Push 1 and 0 in it
pows.Add(0);
pows.Add(1);
// Iterate over all the exponents
for (int p = 2; p < 25; p++) {
// Iterate over all possible numbers
long num = 2;
// This loop will run for a
// maximum of sqrt(R) times
while ((long)(Math.Pow(num, p) + 0.5) <= R) {
// Push this power in
// the array pows[]
pows.Add((long)(Math.Pow(num, p) + 0.5));
// Increase the number
num++;
}
}
// Stores if i can be expressed as
// the sum of perfect power or not
int[] ok = new int[R + 2];
// memset(ok, 0, sizeof(ok));
// Iterate over all possible pairs
// of the array pows[]
for (int i = 0; i < pows.Count; i++) {
for (int j = 0; j < pows.Count; j++) {
if (pows[i] + pows[j] <= R
&& pows[i] + pows[j] >= L) {
// The number is valid
ok[pows[i] + pows[j]] = 1;
}
}
}
// Find the prefix sum of the
// array ok[]
for (int i = 1; i <= R; i++) {
ok[i] += ok[i - 1];
}
// Return the count of required number
return ok[R] - ok[L - 1];
}
// Driver Code
public static void Main()
{
int L = 5, R = 8;
Console.WriteLine(TotalPerfectPowerSum(L, R));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the number of numbers
// that can be expressed in the form of
// the sum of two perfect powers
function TotalPerfectPowerSum(L,
R)
{
// Stores all possible powers
let pows = [];
// Push 1 and 0 in it
pows.push(0);
pows.push(1);
// Iterate over all the exponents
for (let p = 2; p < 25; p++) {
// Iterate over all possible numbers
let num = 2;
// This loop will run for a
// maximum of sqrt(R) times
while (Math.floor(Math.pow(num, p) + 0.5) <= R) {
// Push this power in
// the array pows[]
pows.push(
Math.floor(Math.pow(num, p) + 0.5));
// Increase the number
num++;
}
}
// Stores if i can be expressed as
// the sum of perfect power or not
let ok = new Array(R + 1).fill(0);
// Iterate over all possible pairs
// of the array pows[]
for (let i = 0;
i < pows.length; i++) {
for (let j = 0;
j < pows.length; j++) {
if (pows[i] + pows[j] <= R
&& pows[i] + pows[j] >= L) {
// The number is valid
ok[pows[i] + pows[j]] = 1;
}
}
}
// Find the prefix sum of the
// array ok[]
for (let i = 1; i <= R; i++) {
ok[i] += ok[i - 1];
}
// Return the count of required number
return ok[R] - ok[L - 1];
}
// Driver Code
let L = 5, R = 8;
document.write(TotalPerfectPowerSum(L, R));
// This code is contributed by Potta Lokesh
</script>
Producción:
2
Complejidad de tiempo: O(R*log(R))
Espacio auxiliar: O(R)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA