Dado un rango representado por dos enteros positivos L y R . La tarea es contar los números del rango que tiene MCD de potencias de factores primos iguales a 1. En otras palabras, si un número X tiene su descomposición en factores primos de la forma 2 p 1 * 3 p 2 * 5 p 3 * … entonces el MCD de p 1 , p 2 , p 3 , … debe ser igual a 1 .
Ejemplos:
Entrada: L = 2, R = 5
Salida: 3 2, 3 y 5 son los números requeridos que tienen MCD de potencias de factores primos iguales a 1. 2 = 2 1 3 = 3 1 5 = 5 1Entrada: L = 13, R = 20
Salida: 7
Prerrequisitos: Potencias Perfectas en un Rango
Enfoque ingenuo: iterar sobre todos los números de L a R y factorizar en factores primos cada número y luego calcular el GCD de las potencias de los factores primos. Si GCD = 1 , incremente una variable de conteo y finalmente devuélvala como respuesta.
Enfoque eficiente: la idea clave aquí es notar que los números válidos no son potencias perfectas ya que las potencias de los factores primos son de tal manera que su MCD siempre es mayor que 1. En otras palabras, todas las potencias perfectas no son números válidos. .
Por ejemplo
2500 es potencia perfecta cuya descomposición en factores primos es 2500 = 2 2 * 5 4 . Ahora el MCD de (2, 4) = 2 que es mayor que 1. Si algún número tiene la x -ésima potencia de un factor en su descomposición en factores primos, entonces las potencias de otros factores primos tendrán que ser múltiplos de x para que el número para ser inválido.
Por lo tanto, podemos encontrar el número total de potencias perfectas que se encuentran en el rango y restarlo de los números totales. A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define MAX 1e18
// Vector to store powers greater than 3
vector<long int> powers;
// Set to store perfect squares
set<long int> squares;
// Set to store powers other than perfect squares
set<long int> s;
void powersPrecomputation()
{
for (long int i = 2; i < N; i++) {
// Pushing squares
squares.insert(i * i);
// if the values is already a perfect square means
// present in the set
if (squares.find(i) != squares.end())
continue;
long int temp = i;
// Run loop until some power of current number
// doesn't exceed MAX
while (i * i <= MAX / temp) {
temp *= (i * i);
// Pushing only odd powers as even power of a number
// can always be expressed as a perfect square
// which is already present in set squares
s.insert(temp);
}
}
// Inserting those sorted
// values of set into a vector
for (auto x : s)
powers.push_back(x);
}
long int calculateAnswer(long int L, long int R)
{
// Precompute the powers
powersPrecomputation();
// Calculate perfect squares in
// range using sqrtl function
long int perfectSquares = floor(sqrtl(R)) - floor(sqrtl(L - 1));
// Calculate upper value of R
// in vector using binary search
long int high = upper_bound(powers.begin(),
powers.end(), R)
- powers.begin();
// Calculate lower value of L
// in vector using binary search
long int low = lower_bound(powers.begin(),
powers.end(), L)
- powers.begin();
// Calculate perfect powers
long perfectPowers = perfectSquares + (high - low);
// Compute final answer
long ans = (R - L + 1) - perfectPowers;
return ans;
}
// Driver Code
int main()
{
long int L = 13, R = 20;
cout << calculateAnswer(L, R);
return 0;
}
Java
// Java implementation of above idea
import java.util.*;
class GFG
{
static int N = 1000005;
static long MAX = (long) 1e18;
// Vector to store powers greater than 3
static Vector<Long> powers = new Vector<>();
// Set to store perfect squares
static TreeSet<Long> squares = new TreeSet<>();
// Set to store powers other than perfect squares
static TreeSet<Long> s = new TreeSet<>();
static void powersPrecomputation()
{
for (long i = 2; i < N; i++)
{
// Pushing squares
squares.add(i * i);
// if the values is already a perfect square means
// present in the set
if (squares.contains(i))
continue;
long temp = i;
// Run loop until some power of current number
// doesn't exceed MAX
while (i * i <= MAX / temp)
{
temp *= (i * i);
// Pushing only odd powers as even power of a number
// can always be expressed as a perfect square
// which is already present in set squares
s.add(temp);
}
}
// Inserting those sorted
// values of set into a vector
for (long x : s)
powers.add(x);
}
static long calculateAnswer(long L, long R)
{
// Precompute the powers
powersPrecomputation();
// Calculate perfect squares in
// range using sqrtl function
long perfectSquares = (long) (Math.floor(Math.sqrt(R)) -
Math.floor(Math.sqrt(L - 1)));
// Calculate upper value of R
// in vector using binary search
long high = Collections.binarySearch(powers, R);
// Calculate lower value of L
// in vector using binary search
long low = Collections.binarySearch(powers, L);
// Calculate perfect powers
long perfectPowers = perfectSquares + (high - low);
// Compute final answer
long ans = (R - L + 1) - perfectPowers;
return ans;
}
// Driver Code
public static void main(String[] args)
{
long L = 13, R = 20;
System.out.println(calculateAnswer(L, R));
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python3 implementation of the approach from bisect import bisect as upper_bound from bisect import bisect_left as lower_bound from math import floor N = 1000005 MAX = 10**18 # Vector to store powers greater than 3 powers = [] # Set to store perfect squares squares = dict() # Set to store powers other than perfect squares s = dict() def powersPrecomputation(): for i in range(2, N): # Pushing squares squares[i * i] = 1 # if the values is already a perfect square means # present in the set if (i not in squares.keys()): continue temp = i # Run loop until some power of current number # doesn't exceed MAX while (i * i <= (MAX // temp)): temp *= (i * i) # Pushing only odd powers as even power of a number # can always be expressed as a perfect square # which is already present in set squares s[temp]=1 # Inserting those sorted # values of set into a vector for x in s: powers.append(x) def calculateAnswer(L, R): # Precompute the powers powersPrecomputation() # Calculate perfect squares in # range using sqrtl function perfectSquares = floor((R)**(.5)) - floor((L - 1)**(.5)) # Calculate upper value of R # in vector using binary search high = upper_bound(powers,R) # Calculate lower value of L # in vector using binary search low = lower_bound(powers,L) # Calculate perfect powers perfectPowers = perfectSquares + (high - low) # Compute final answer ans = (R - L + 1) - perfectPowers return ans # Driver Code L = 13 R = 20 print(calculateAnswer(L, R)) # This code is contributed by mohit kumar 29
C#
// C# implementation of above idea
using System;
using System.Collections.Generic;
public class GFG
{
static int N = 100005;
static long MAX = (long) 1e18;
// List to store powers greater than 3
static List<long> powers = new List<long>();
// Set to store perfect squares
static HashSet<long> squares = new HashSet<long>();
// Set to store powers other than perfect squares
static HashSet<long> s = new HashSet<long>();
static void powersPrecomputation()
{
for (long i = 2; i < N; i++)
{
// Pushing squares
squares.Add(i * i);
// if the values is already a perfect square means
// present in the set
if (squares.Contains(i))
continue;
long temp = i;
// Run loop until some power of current number
// doesn't exceed MAX
while (i * i <= MAX / temp)
{
temp *= (i * i);
// Pushing only odd powers as even power of a number
// can always be expressed as a perfect square
// which is already present in set squares
s.Add(temp);
}
}
// Inserting those sorted
// values of set into a vector
foreach (long x in s)
powers.Add(x);
}
static long calculateAnswer(long L, long R)
{
// Precompute the powers
powersPrecomputation();
// Calculate perfect squares in
// range using sqrtl function
long perfectSquares = (long) (Math.Floor(Math.Sqrt(R)) -
Math.Floor(Math.Sqrt(L - 1)));
// Calculate upper value of R
// in vector using binary search
long high = Array.BinarySearch(powers.ToArray(), R);
// Calculate lower value of L
// in vector using binary search
long low = Array.BinarySearch(powers.ToArray(), L);
// Calculate perfect powers
long perfectPowers = perfectSquares + (high - low);
// Compute readonly answer
long ans = (R - L + 1) - perfectPowers;
return ans;
}
// Driver Code
public static void Main(String[] args)
{
long L = 13, R = 20;
Console.WriteLine(calculateAnswer(L, R));
}
}
// This code is contributed by 29AjayKumar
Javascript
// JavaScript implementation of the approach
let N = 1000005;
let MAX = 1e18;
// Vector to store powers greater than 3
let powers = [];
// Set to store perfect squares
let squares = new Set();
// Set to store powers other than perfect squares
let s = new Set();
function upper_bound(arr, value)
{
for (let i = 0; i < arr.length; i++)
{
if (arr[i] > value)
return i;
}
return arr.length;
}
function lower_bound(arr, value)
{
for (let i = 0; i < arr.length; i++)
{
if (arr[i] >= value)
return i;
}
return arr.length;
}
function powersPrecomputation()
{
for (let i = 2; i < N; i++) {
// Pushing squares
squares.add(i * i);
// if the values is already a perfect square means
// present in the set
if (squares.has(i))
continue;
let temp = i;
// Run loop until some power of current number
// doesn't exceed MAX
while (i * i <= MAX / temp) {
temp *= (i * i);
// Pushing only odd powers as even power of a number
// can always be expressed as a perfect square
// which is already present in set squares
s.add(temp);
}
}
// Inserting those sorted
// values of set into a vector
for (let x of s)
powers.push(x);
}
function calculateAnswer(L, R)
{
// Precompute the powers
powersPrecomputation();
// Calculate perfect squares in
// range using sqrtl function
let perfectSquares = Math.floor(Math.sqrt(R)) - Math.floor(Math.sqrt(L - 1));
// Calculate upper value of R
// in vector using binary search
let high = upper_bound(powers, R);
// Calculate lower value of L
// in vector using binary search
let low = lower_bound(powers, L);
// Calculate perfect powers
let perfectPowers = perfectSquares + (high - low);
// Compute final answer
let ans = (R - L + 1) - perfectPowers;
return ans;
}
// Driver Code
let L = 13, R = 20;
console.log(calculateAnswer(L, R));
// This code is contributed by phasing17
Producción:
7
Complejidad de Tiempo: O(N * log N), para iterar sobre N
Espacio Auxiliar: O(N), ya que se ha tomado N espacio extra.
Publicación traducida automáticamente
Artículo escrito por Nishant Tanwar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA