Dada una array arr[] de longitud N y un entero K , la tarea es contar pares en la array cuyo producto es K- ésima potencia de un entero positivo, es decir
A[i] * A[j] = Z K para cualquier entero positivo Z.
Ejemplos:
Entrada: arr[] = {1, 3, 9, 8, 24, 1}, K = 3
Salida: 5
Explicación: Hay 5 pares de este tipo, que se pueden representar como Z 3 – A[0] * A[3] = 1 * 8 = 2^3 A[0] * A[5] = 1 * 1 = 1^3 A[1] * A[2] = 3 * 9 = 3^3 A[2] * A[4] = 9 * 24 = 6^3 A[3] * A[5] = 8 * 1 = 2^ 3
Entrada: arr[] = {7, 4, 10, 9, 2, 8, 8, 7, 3, 7}, K = 2
Salida: 7
Explicación: Hay 7 de esos pares, que se pueden representar como Z 2
Enfoque: La observación clave en este problema es para representar cualquier número en la forma de Z K , entonces las potencias de descomposición en factores primos de ese número deben ser múltiplos de K. A continuación se muestra la ilustración de los pasos:
- Calcule la descomposición en factores primos de cada número de la array y almacene los factores primos en forma de par clave-valor en un mapa hash, donde la clave será un factor primo de ese elemento y el valor será la potencia elevada a ese primo factor módulo K, en la descomposición en factores primos de ese número.
Por ejemplo:
Given Element be - 360 and K = 2
Prime Factorization = 23 * 32 * 51
Key-value pairs for this would be,
=> {(2, 3 % 2), (3, 2 % 2),
(5, 1 % 2)}
=> {(2, 1), (5, 1)}
// Notice that prime number 3
// is ignored because of the
// modulus value was 0
- Recorra la array y cree un mapa hash de frecuencia en el que los pares clave-valor se definirían de la siguiente manera:
Key: Prime Factors pairs mod K Value: Frequency of this Key
- Finalmente, Traverse para cada elemento de la array y verificar que los factores primos requeridos estén presentes en el mapa hash o no. En caso afirmativo, habrá F número de pares posibles, donde F es la frecuencia.
Ejemplo:
Given Number be - 360, K = 3
Prime Factorization -
=> {(3, 2), (5, 1)}
Required Prime Factors -
=> {(p1, K - val1), ...(pn, K - valn)}
=> {(3, 3 - 2), (5, 3 - 1)}
=> {(3, 1), (5, 2)}
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count the
// pairs whose product is Kth
// power of some integer Z
#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
// Smallest prime factor
int spf[MAXN];
// Sieve of eratosthenes
// for computing primes
void sieve()
{
int i, j;
spf[1] = 1;
for (i = 2; i < MAXN; i++)
spf[i] = i;
// Loop for markig the factors
// of prime number as non-prime
for (i = 2; i < MAXN; i++) {
if (spf[i] == i) {
for (j = i * 2;
j < MAXN; j += i) {
if (spf[j] == j)
spf[j] = i;
}
}
}
}
// Function to factorize the
// number N into its prime factors
vector<pair<int, int> > getFact(int x)
{
// Prime factors along with powers
vector<pair<int, int> > factors;
// Loop while the X is not
// equal to 1
while (x != 1) {
// Smallest prime
// factor of x
int z = spf[x];
int cnt = 0;
// Count power of this
// prime factor in x
while (x % z == 0)
cnt++, x /= z;
factors.push_back(
make_pair(z, cnt));
}
return factors;
}
// Function to count the pairs
int pairsWithKth(int a[], int n, int k)
{
// Precomputation
// for factorisation
sieve();
int answer = 0;
// Data structure for storing
// list L for each element along
// with frequency of occurrence
map<vector<pair<int,
int> >,
int>
count_of_L;
// Loop to iterate over the
// elements of the array
for (int i = 0; i < n; i++) {
// Factorise each element
vector<pair<int, int> >
factors = getFact(a[i]);
sort(factors.begin(),
factors.end());
vector<pair<int, int> > L;
// Loop to iterate over the
// factors of the element
for (auto it : factors) {
if (it.second % k == 0)
continue;
L.push_back(
make_pair(
it.first,
it.second % k));
}
vector<pair<int, int> > Lx;
// Loop to find the required prime
// factors for each element of array
for (auto it : L) {
// Represents how much remainder
// power needs to be added to
// this primes power so as to make
// it a multiple of k
Lx.push_back(
make_pair(
it.first,
(k - it.second + k) % k));
}
// Add occurrences of
// Lx till now to answer
answer += count_of_L[Lx];
// Increment the counter for L
count_of_L[L]++;
}
return answer;
}
// Driver Code
int main()
{
int n = 6;
int a[n] = { 1, 3, 9, 8, 24, 1 };
int k = 3;
cout << pairsWithKth(a, n, k);
return 0;
}
5
Complejidad del tiempo: O(N * log 2 N)