Dado un entero positivo N , la tarea es encontrar el número de tripletes (X, Y, Z) tales que la suma del producto de dos números cualesquiera con el tercer número sea N .
Ejemplos:
Entrada: N = 2
Salida: 1
Explicación:
Los únicos tripletes que satisfacen los criterios dados son (1, 1, 1). Por lo tanto, la cuenta es 1.Entrada: N = 3
Salida: 3
Enfoque: Este problema dado se puede resolver reorganizando la ecuación como:
Considere un triplete como (X, Y, Z) entonces
=>
=>
A partir de la ecuación anterior, la idea es iterar sobre todos los valores posibles de Z en el rango [1, N] y sumar el recuento de todos los posibles de X e Y calculando el factor primo de (N – Z) que satisface la ecuación anterior. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, countTriplets para almacenar el recuento resultante de trillizos que satisfagan los criterios dados.
- Encuentre el factor primo más pequeño para todos los elementos en el rango [1, 10 5 ] usando la Tamiz de Eratóstenes .
- Itere sobre el rango [1, N] usando la variable, diga K y realice los siguientes pasos:
- Encuentre el número de pares cuyo producto es (N – K) usando el enfoque discutido en este artículo y agregue el conteo obtenido a la variable conteoTriplets .
- Después de completar los pasos anteriores, imprima el valor de countTriplets como el conteo resultante de trillizos.
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;
vector<int> s(11,0);
// Function to find the SPF[i] using the
// Sieve Of Eratosthenes
void sieveOfEratosthenes(int N){
// Stores whether i is prime or not
bool prime[N+1];
memset(prime,false,sizeof(false));
// Initializing smallest factor as
// 2 for all even numbers
for (int i=2;i< N + 1; i+=2)
s[i] = 2;
// Iterate for all odd numbers < N
for(int i =3;i<N + 1;i+=2){
if (prime[i] == false){
// SPF of i for a prime is
// the number itself
s[i] = i;
// Iterate for all the multiples
// of the current prime number
for(int j= i;j< N / i + 1; j+=2){
if (prime[i * j] == false){
prime[i * j] = true;
// The value i is smallest
// prime factor for i * j
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and its power
int generatePrimeFactors(int N){
// Current prime factor of N
int curr = s[N];
// Stores the powers of the current
// prime factor
map<int,int> cnt;
cnt[s[N]] = 1;
// Find all the prime factors and
// their powers
while (N > 1){
N /= s[N];
if (N and s[N])
if(cnt.find(s[N]) == cnt.end())
cnt[s[N]] = 1;
else
cnt[s[N]] += 1;
}
if (cnt.find(0) != cnt.end())
cnt.erase(0);
int totfactor = 1;
for (auto i: cnt)
totfactor *= i.second + 1;
// Return the total count of factors
return totfactor;
}
// Function to count the number of triplets
// satisfying the given criteria
int countTriplets(int N){
// Stores the count of resultant triplets
int CountTriplet = 0;
for (int z=1;z<N + 1;z++){
// Add the count all factors of N-z
// to the variable CountTriplet
int p = generatePrimeFactors(N-z);
if (p > 1)
CountTriplet += p;
}
// Return total count of triplets
return CountTriplet + 1;
}
// Driver Code
int main(){
int N = 10;
// S[i] stores the smallest prime factor
// for each element i
// Find the SPF[i]
sieveOfEratosthenes(N);
// Function Call
cout<<countTriplets(N);
}
// This code is contributed by SURENDRA_GANGWAR.
Java
// Java program for the above approach
import java.util.*;
class GFG{
static int[] s = new int[11];
// Function to find the SPF[i] using the
// Sieve Of Eratosthenes
static void sieveOfEratosthenes(int N){
// Stores whether i is prime or not
boolean []prime = new boolean[N+1];
// Initializing smallest factor as
// 2 for all even numbers
for (int i = 2; i < N + 1; i += 2)
s[i] = 2;
// Iterate for all odd numbers < N
for(int i = 3; i < N + 1; i += 2){
if (prime[i] == false){
// SPF of i for a prime is
// the number itself
s[i] = i;
// Iterate for all the multiples
// of the current prime number
for(int j= i; j < N / i + 1; j += 2){
if (prime[i * j] == false){
prime[i * j] = true;
// The value i is smallest
// prime factor for i * j
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and its power
static int generatePrimeFactors(int N){
// Current prime factor of N
int curr = s[N];
// Stores the powers of the current
// prime factor
HashMap<Integer,Integer> cnt = new HashMap<>();
cnt.put(s[N],1);
// Find all the prime factors and
// their powers
while (N > 1){
N /= s[N];
if (N != 0 && s[N] != 0)
if(!cnt.containsKey(s[N]))
cnt.put(s[N], 1);
else
cnt.put(s[N], cnt.get(s[N]) + 1);
}
if (cnt.containsKey(0))
cnt.remove(0);
int totfactor = 1;
for (Map.Entry<Integer,Integer> i : cnt.entrySet())
totfactor *= i.getValue() + 1;
// Return the total count of factors
return totfactor;
}
// Function to count the number of triplets
// satisfying the given criteria
static int countTriplets(int N){
// Stores the count of resultant triplets
int CountTriplet = 0;
for (int z=1;z<N + 1;z++){
// Add the count all factors of N-z
// to the variable CountTriplet
int p = generatePrimeFactors(N-z);
if (p > 1)
CountTriplet += p;
}
// Return total count of triplets
return CountTriplet + 1;
}
// Driver Code
public static void main(String[] args){
int N = 10;
// S[i] stores the smallest prime factor
// for each element i
// Find the SPF[i]
sieveOfEratosthenes(N);
// Function Call
System.out.print(countTriplets(N));
}
}
// This code is contributed by gauravrajput1
Python3
# Python program for the above approach
# Function to find the SPF[i] using the
# Sieve Of Eratosthenes
def sieveOfEratosthenes(N, s):
# Stores whether i is prime or not
prime = [False] * (N + 1)
# Initializing smallest factor as
# 2 for all even numbers
for i in range(2, N + 1, 2):
s[i] = 2
# Iterate for all odd numbers < N
for i in range(3, N + 1, 2):
if (prime[i] == False):
# SPF of i for a prime is
# the number itself
s[i] = i
# Iterate for all the multiples
# of the current prime number
for j in range(i, int(N / i) + 1, 2):
if (prime[i * j] == False):
prime[i * j] = True
# The value i is smallest
# prime factor for i * j
s[i * j] = i
# Function to generate prime factors
# and its power
def generatePrimeFactors(N):
# Current prime factor of N
curr = s[N]
# Stores the powers of the current
# prime factor
cnt = {s[N]:1}
# Find all the prime factors and
# their powers
while (N > 1):
N //= s[N]
if N and s[N]:
if cnt.get(s[N], 0) == 0:
cnt[s[N]] = 1
else:
cnt[s[N]] += 1
if 0 in cnt:
cnt.pop(0)
totfactor = 1
for i in cnt.values():
totfactor *= i + 1
# Return the total count of factors
return totfactor
# Function to count the number of triplets
# satisfying the given criteria
def countTriplets(N):
# Stores the count of resultant triplets
CountTriplet = 0
for z in range(1, N + 1):
# Add the count all factors of N-z
# to the variable CountTriplet
p = generatePrimeFactors(N-z)
if p > 1:
CountTriplet += p
# Return total count of triplets
return CountTriplet + 1
# Driver Code
N = 10
# S[i] stores the smallest prime factor
# for each element i
s = [0] * (N + 1)
# Find the SPF[i]
sieveOfEratosthenes(N, s)
# Function Call
print(countTriplets(N))
Javascript
<script>
// Javascript program for the above approach
let s = new Array(11).fill(0)
// Function to find the SPF[i] using the
// Sieve Of Eratosthenes
function sieveOfEratosthenes(N){
// Stores whether i is prime or not
let prime = new Array(N+1).fill(false);
// Initializing smallest factor as
// 2 for all even numbers
for (let i = 2; i < N + 1; i += 2)
s[i] = 2;
// Iterate for all odd numbers < N
for(let i = 3; i < N + 1; i += 2){
if (prime[i] == false){
// SPF of i for a prime is
// the number itself
s[i] = i;
// Iterate for all the multiples
// of the current prime number
for(let j= i; j < Math.floor(N / i + 1); j += 2){
if (prime[i * j] == false){
prime[i * j] = true;
// The value i is smallest
// prime factor for i * j
s[i * j] = i;
}
}
}
}
}
// Function to generate prime factors
// and its power
function generatePrimeFactors(N)
{
// Current prime factor of N
let curr = s[N];
// Stores the powers of the current
// prime factor
let cnt = new Map();
cnt.set(s[N],1);
// Find all the prime factors and
// their powers
while (N > 1){
N = Math.floor(N / s[N]);
if (N != 0 && s[N] != 0)
if(!cnt.has(s[N]))
cnt.set(s[N], 1);
else
cnt.set(s[N], cnt.get(s[N]) + 1);
}
if (cnt.has(0))
cnt.delete(0);
let totfactor = 1;
for (i of cnt.values())
totfactor *= i + 1;
// Return the total count of factors
return totfactor;
}
// Function to count the number of triplets
// satisfying the given criteria
function countTriplets(N){
// Stores the count of resultant triplets
let CountTriplet = 0;
for (let z=1;z<N + 1;z++){
// Add the count all factors of N-z
// to the variable CountTriplet
let p = generatePrimeFactors(N-z);
if (p > 1)
CountTriplet += p;
}
// Return total count of triplets
return CountTriplet + 1;
}
// Driver Code
let N = 10;
// S[i] stores the smallest prime factor
// for each element i
// Find the SPF[i]
sieveOfEratosthenes(N);
// Function Call
document.write((countTriplets(N)));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
23
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aviral4srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA