Dada una array arr[] de N enteros. El valor de un subconjunto de la array A se define como el producto de todos los números primos de ese subconjunto. Si no hay números primos en el subconjunto, entonces el valor de ese subconjunto es 1 . La tarea es calcular el producto de los valores de todos los posibles subconjuntos no vacíos del módulo de array dado 100000007 .
Ejemplos:
Entrada: arr[] = {3, 7}
Salida: 441
val({3}) = 3
val({7}) = 7
val({3, 7}) = 3 * 7 = 21
3 * 7 * 21 = 441
Entrada: arr[] = {1, 1, 1}
Salida: 1
Enfoque: Dado que se sabe que un número aparece 2 N – 1 veces en todo el subconjunto de la array dada de tamaño N . Entonces, si un número X es primo, la contribución de X será X * X * X * ….. * 2 N – 1 veces, es decir
Dado que 2 N – 1 también será un número grande, no se puede calcular directamente. Aquí se utilizará el teorema de Fermat para calcular la potencia.
Después de eso, el valor de cada elemento se puede calcular fácilmente.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include<bits/stdc++.h>
using namespace std;
int power(int a, int b, int mod)
{
int aa = 1;
while(b)
{
if(b & 1)
{
aa = aa * a;
aa %= mod;
}
a = a * a;
a %= mod;
b /= 2;
}
return aa;
}
// Function to return the prime subset
// product of the given array
int product(int A[], int n)
{
// Create Sieve to check whether a
// number is prime or not
int N = 100010;
int mod = 1000000007;
vector<int> prime(N, 1);
prime[0] = prime[1] = 0;
int i = 2;
while (i * i < N)
{
if (prime[i])
for (int j = 2 * i;
j <= N;j += i)
prime[j] = 0;
i += 1;
}
// Length of the array
// Calculating 2^(n-1) % mod
int t = power(2, n - 1, mod - 1);
int ans = 1;
for (int j = 0; j < n; j++)
{
int i = A[j];
// If element is prime then add
// its contribution in the result
if( prime[i])
{
ans *= power(i, t, mod);
ans %= mod;
}
}
return ans;
}
// Driver code
int main()
{
int A[] = {3, 7};
int n = sizeof(A) / sizeof(A[0]);
printf("%d", product(A, n));
}
// This code is contributed by Mohit Kumar
Java
// Java implementation of the approach
class GFG
{
static int power(int a, int b, int mod)
{
int aa = 1;
while(b > 0)
{
if(b % 2 == 1)
{
aa = aa * a;
aa %= mod;
}
a = a * a;
a %= mod;
b /= 2;
}
return aa;
}
// Function to return the prime subset
// product of the given array
static int product(int A[], int n)
{
// Create Sieve to check whether a
// number is prime or not
int N = 100010;
int mod = 1000000007;
int []prime = new int[N];
for (int j = 0; j < N; j++)
{
prime[j] = 1;
}
prime[0] = prime[1] = 0;
int i = 2;
while (i * i < N)
{
if (prime[i] == 1)
for (int j = 2 * i;
j < N;j += i)
prime[j] = 0;
i += 1;
}
// Length of the array
// Calculating 2^(n-1) % mod
int t = power(2, n - 1, mod - 1);
int ans = 1;
for (int j = 0; j < n; j++)
{
i = A[j];
// If element is prime then add
// its contribution in the result
if( prime[i] == 1)
{
ans *= power(i, t, mod);
ans %= mod;
}
}
return ans;
}
// Driver code
public static void main (String[] args)
{
int A[] = {3, 7};
int n = A.length;
System.out.printf("%d", product(A, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach # Function to return the prime subset # product of the given array def product(A): # Create Sieve to check whether a # number is prime or not N = 100010 mod = 1000000007 prime = [1] * N prime[0] = prime[1] = 0 i = 2 while i * i < N: if prime[i]: for j in range(i * i, N, i): prime[j] = 0 i += 1 # Length of the array n = len(A) # Calculating 2^(n-1) % mod t = pow(2, n-1, mod-1) ans = 1 for i in A: # If element is prime then add # its contribution in the result if prime[i]: ans *= pow(i, t, mod) ans %= mod return ans # Driver code A = [3, 7] print(product(A))
C#
// C# implementation of the approach
using System;
class GFG
{
static int power(int a, int b, int mod)
{
int aa = 1;
while(b > 0)
{
if(b % 2 == 1)
{
aa = aa * a;
aa %= mod;
}
a = a * a;
a %= mod;
b /= 2;
}
return aa;
}
// Function to return the prime subset
// product of the given array
static int product(int []A, int n)
{
// Create Sieve to check whether a
// number is prime or not
int N = 100010;
int mod = 1000000007;
int []prime = new int[N];
for (int j = 0; j < N; j++)
{
prime[j] = 1;
}
prime[0] = prime[1] = 0;
int i = 2;
while (i * i < N)
{
if (prime[i] == 1)
for (int j = 2 * i;
j < N; j += i)
prime[j] = 0;
i += 1;
}
// Length of the array
// Calculating 2^(n-1) % mod
int t = power(2, n - 1, mod - 1);
int ans = 1;
for (int j = 0; j < n; j++)
{
i = A[j];
// If element is prime then add
// its contribution in the result
if( prime[i] == 1)
{
ans *= power(i, t, mod);
ans %= mod;
}
}
return ans;
}
// Driver code
public static void Main(String[] args)
{
int []A = {3, 7};
int n = A.Length;
Console.Write("{0}", product(A, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
function power(a, b, mod) {
let aa = 1;
while (b) {
if (b & 1) {
aa = aa * a;
aa %= mod;
}
a = a * a;
a %= mod;
b = Math.floor(b / 2);
}
return aa;
}
// Function to return the prime subset
// product of the given array
function product(A, n) {
// Create Sieve to check whether a
// number is prime or not
let N = 100010;
let mod = 1000000007;
let prime = new Array(N).fill(1);
prime[0] = prime[1] = 0;
let i = 2;
while (i * i < N) {
if (prime[i])
for (let j = 2 * i;
j <= N; j += i)
prime[j] = 0;
i += 1;
}
// Length of the array
// Calculating 2^(n-1) % mod
let t = power(2, n - 1, mod - 1);
let ans = 1;
for (let j = 0; j < n; j++) {
let i = A[j];
// If element is prime then add
// its contribution in the result
if (prime[i]) {
ans *= power(i, t, mod);
ans %= mod;
}
}
return ans;
}
// Driver code
let A = [3, 7];
let n = A.length;
document.write(product(A, n));
// This code is contributed by Saurabh Jaiswal
</script>
Producción:
441