Dados dos arreglos A[] y B[] que consisten en N y M enteros respectivamente, la tarea es contar pares (A[i], B[j]) de modo que el producto de su conteo de factores primos distintos sea par.
Ejemplos:
Entrada: A[] = {1, 2, 3}, B[] = {4, 5, 6}, N = 3, M = 3
Salida: 2
Explicación:
- Reemplazar todos los elementos de la array con el recuento de sus distintos factores primos modifica las arrays a A[] = {0, 1, 1} y B[] = {1, 1, 2}.
- Por lo tanto, los pares totales con producto par son {{2, 6}, {3, 6}}.
Entrada: A[] = {1, 7}, B[] = {5, 6}, N = 2, M = 2
Salida: 1
Explicación:
- Reemplazar todos los elementos de la array con el recuento de sus distintos factores primos modifica las arrays a A[] = {0, 1} y B[] = {1, 2}.
- Por lo tanto, el total de pares con producto par es {7, 6}.
Enfoque ingenuo: el enfoque más simple es generar todos los pares posibles (A[i], B[j]) a partir de ambos arreglos y para cada par, calcular el recuento de factores primos distintos de los elementos del arreglo y verificar si su producto es par . O no. Si se encuentra que es cierto, entonces incremente el conteo de dichos pares.
Complejidad de Tiempo: O(N 5/2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar precalculando el recuento de distintos factores primos de todos los números hasta el elemento más grande de ambas arrays y utilizando la siguiente propiedad del producto de dos números:
- Impar * Impar = Impar
- par * impar = par
- Impar * Par = Par
- par * par = par
Siga los pasos a continuación para resolver el problema:
- Primero, calcule factores primos distintos de todos los números hasta MAX y guárdelo en vector<int> digamos countDistinct.
- Inicialice dos variables, digamos evenCount y oddCount, para almacenar el recuento de elementos con recuentos pares e impares de distintos factores primos de los elementos de la array en B[] .
- Recorre la array B[]. Si countDistinct[B[i]] = 0 , omita este paso. Si es impar, incremente oddCount en 1. De lo contrario, incremente evenCount en uno.
- Inicialice una variable evenPairs a 0 .
- Recorra la array A[] e incremente evenPairs por evenCount si countDistinct[A[i]] es impar.
- De lo contrario, incremente evenPairs por evenCount + oddCount.
- Imprime el valor de evenPairs.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000000
// Function to calculate count of
// distinct prime factors of a number
void countOfPrimefactors(vector<int>& CountDistinct)
{
bool prime[MAX + 1];
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
// Sieve of Eratosthenes
for (long long int i = 2; i <= MAX; i++) {
if (prime[i] == true) {
CountDistinct[i] = 1;
for (long long int j = i * 2; j <= MAX;
j += i) {
CountDistinct[j]++;
prime[j] = false;
}
}
}
}
// Function to count pairs with even
// product of distinct prime factors
int CountEvenPair(int A[], int B[], int N, int M)
{
// Stores count of
// distinct prime factors
vector<int> countDistinct(MAX + 1);
countOfPrimefactors(countDistinct);
// Stores the count of numbers
// with even prime factors in B[]
int evenCount = 0;
// Stores the count of numbers
// with odd prime factors in B[]
int oddCount = 0;
// Even Product Pairs
int evenPairs = 0;
// Traverse the array B[]
for (int i = 0; i < M; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[B[i]] == 0)
continue;
// If count of prime factors is odd
if (countDistinct[B[i]] & 1) {
// Increment oddCount by 1
oddCount++;
}
else {
// Increment evenCount by 1
evenCount++;
}
}
for (int i = 0; i < N; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[A[i]] == 0)
continue;
// If count of prime factors is odd
if (countDistinct[A[i]] & 1) {
// odd * even = even
evenPairs += (evenCount);
}
// If count of prime factors is even
else {
// even * odd = even
// even * even = even
evenPairs += evenCount + oddCount;
}
}
return evenPairs;
}
// Driver Code
int main()
{
int A[] = { 1, 2, 3 };
int B[] = { 4, 5, 6 };
int N = sizeof(A) / sizeof(A[0]);
int M = sizeof(B) / sizeof(B[0]);
cout << CountEvenPair(A, B, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
static int MAX = 1000000;
// Function to calculate count of
// distinct prime factors of a number
static void countOfPrimefactors(int[] CountDistinct)
{
boolean[] prime = new boolean[MAX + 1];
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
// Sieve of Eratosthenes
for (int i = 2; i <= MAX; i++) {
if (prime[i] == true) {
CountDistinct[i] = 1;
for (int j = i * 2; j <= MAX;
j += i) {
CountDistinct[j]++;
prime[j] = false;
}
}
}
}
// Function to count pairs with even
// product of distinct prime factors
static int CountEvenPair(int A[], int B[], int N, int M)
{
// Stores count of
// distinct prime factors
int[] countDistinct = new int[(MAX + 1)];
countOfPrimefactors(countDistinct);
// Stores the count of numbers
// with even prime factors in B[]
int evenCount = 0;
// Stores the count of numbers
// with odd prime factors in B[]
int oddCount = 0;
// Even Product Pairs
int evenPairs = 0;
// Traverse the array B[]
for (int i = 0; i < M; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[B[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[B[i]] & 1) != 0) {
// Increment oddCount by 1
oddCount++;
}
else {
// Increment evenCount by 1
evenCount++;
}
}
for (int i = 0; i < N; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[A[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[A[i]] & 1) != 0) {
// odd * even = even
evenPairs += (evenCount);
}
// If count of prime factors is even
else {
// even * odd = even
// even * even = even
evenPairs += evenCount + oddCount;
}
}
return evenPairs;
}
// Driver Code
public static void main(String[] args)
{
int A[] = { 1, 2, 3 };
int B[] = { 4, 5, 6 };
int N = A.length;
int M = B.length;
System.out.println(CountEvenPair(A, B, N, M));
}
}
// This code is contributed by sanjoy_62.
Python3
# Python 3 implementation of # the above approach MAX = 1000000 # Function to calculate count of # distinct prime factors of a number def countOfPrimefactors(CountDistinct): global MAX prime = [0 for i in range(MAX + 1)] for i in range(MAX+1): CountDistinct[i] = 0 prime[i] = True # Sieve of Eratosthenes for i in range(2,MAX+1,1): if (prime[i] == True): CountDistinct[i] = 1 for j in range(i * 2,MAX+1,i): CountDistinct[j] += 1 prime[j] = False # Function to count pairs with even # product of distinct prime factors def CountEvenPair(A, B, N, M): global MAX # Stores count of # distinct prime factors countDistinct = [0 for i in range(MAX + 1)] countOfPrimefactors(countDistinct) # Stores the count of numbers # with even prime factors in B[] evenCount = 0 # Stores the count of numbers # with odd prime factors in B[] oddCount = 0 # Even Product Pairs evenPairs = 0 # Traverse the array B[] for i in range(M): # Since, product has to be # positive i.e > 0 if (countDistinct[B[i]] == 0): continue # If count of prime factors is odd if (countDistinct[B[i]] & 1): # Increment oddCount by 1 oddCount += 1 else: # Increment evenCount by 1 evenCount += 1 for i in range(N): # Since, product has to be # positive i.e > 0 if (countDistinct[A[i]] == 0): continue # If count of prime factors is odd if (countDistinct[A[i]] & 1): # odd * even = even evenPairs += (evenCount) # If count of prime factors is even else: # even * odd = even # even * even = even evenPairs += evenCount + oddCount return evenPairs # Driver Code if __name__ == '__main__': A = [1, 2, 3] B = [4, 5, 6] N = len(A) M = len(B) print(CountEvenPair(A, B, N, M)) # This code is contributed by SURENDRA_GANGWAR.
C#
// C# program for the above approach
using System;
public class GFG
{
static int MAX = 1000000;
// Function to calculate count of
// distinct prime factors of a number
static void countOfPrimefactors(int[] CountDistinct)
{
bool[] prime = new bool[MAX + 1];
for (int i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
// Sieve of Eratosthenes
for (int i = 2; i <= MAX; i++) {
if (prime[i] == true) {
CountDistinct[i] = 1;
for (int j = i * 2; j <= MAX;
j += i) {
CountDistinct[j]++;
prime[j] = false;
}
}
}
}
// Function to count pairs with even
// product of distinct prime factors
static int CountEvenPair(int []A, int []B, int N, int M)
{
// Stores count of
// distinct prime factors
int[] countDistinct = new int[(MAX + 1)];
countOfPrimefactors(countDistinct);
// Stores the count of numbers
// with even prime factors in B[]
int evenCount = 0;
// Stores the count of numbers
// with odd prime factors in B[]
int oddCount = 0;
// Even Product Pairs
int evenPairs = 0;
// Traverse the array B[]
for (int i = 0; i < M; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[B[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[B[i]] & 1) != 0) {
// Increment oddCount by 1
oddCount++;
}
else {
// Increment evenCount by 1
evenCount++;
}
}
for (int i = 0; i < N; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[A[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[A[i]] & 1) != 0) {
// odd * even = even
evenPairs += (evenCount);
}
// If count of prime factors is even
else {
// even * odd = even
// even * even = even
evenPairs += evenCount + oddCount;
}
}
return evenPairs;
}
// Driver Code
public static void Main(string[] args)
{
int []A = { 1, 2, 3 };
int []B = { 4, 5, 6 };
int N = A.Length;
int M = B.Length;
Console.WriteLine(CountEvenPair(A, B, N, M));
}
}
// This code is contributed by AnkThon
Javascript
<script>
// js program for the above approach
let countDistinct = Array(1000000 + 1);
// Function to calculate count of
// distinct prime factors of a number
function countOfPrimefactors(CountDistinct)
{
let MAX = 1000000;
let prime = Array(MAX + 1);
for (let i = 0; i <= MAX; i++) {
CountDistinct[i] = 0;
prime[i] = true;
}
// Sieve of Eratosthenes
for (let i = 2; i <= MAX; i++) {
if (prime[i] == true) {
CountDistinct[i] = 1;
for (let j = i * 2; j <= MAX;
j += i) {
CountDistinct[j]++;
prime[j] = false;
}
}
}
}
// Function to count pairs with even
// product of distinct prime factors
function CountEvenPair(A,B,N,M)
{
let MAX = 1000000;
// Stores count of
// distinct prime factors
countOfPrimefactors(countDistinct);
// Stores the count of numbers
// with even prime factors in B[]
let evenCount = 0;
// Stores the count of numbers
// with odd prime factors in B[]
let oddCount = 0;
// Even Product Pairs
let evenPairs = 0;
// Traverse the array B[]
for (let i = 0; i < M; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[B[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[B[i]] & 1) != 0) {
// Increment oddCount by 1
oddCount++;
}
else {
// Increment evenCount by 1
evenCount++;
}
}
for (let i = 0; i < N; i++) {
// Since, product has to be
// positive i.e > 0
if (countDistinct[A[i]] == 0)
continue;
// If count of prime factors is odd
if ((countDistinct[A[i]] & 1) != 0) {
// odd * even = even
evenPairs += (evenCount);
}
// If count of prime factors is even
else {
// even * odd = even
// even * even = even
evenPairs += evenCount + oddCount;
}
}
return evenPairs;
}
// Driver Code
let A = [1, 2, 3];
let B = [4, 5, 6];
let N = A.length;
let M = B.length;
document.write(CountEvenPair(A, B, N, M));
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por sourav2901 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA