Dado un número N , la tarea es encontrar la suma del producto de elementos de todos los subconjuntos posibles formados por solo divisores de N .
Ejemplos:
Entrada: N = 3
Salida: 7
Explicación:
Los divisores de 3 son 1 y 3. Todos los subconjuntos posibles son {1}, {3}, {1, 3}.
Por tanto, la suma del producto de todos los subconjuntos posibles es:
(1 + 3 + (1 * 3)) = 7.
Entrada: N = 4
Salida: 29
Explicación:
Los divisores de 4 son 1, 2 y 4. Todos los subconjuntos posibles son {1}, {2}, {4}, {1, 2}, {1, 4}, {2, 4}, {1, 2, 4}.
Por lo tanto, la suma del producto de todos los subconjuntos posibles es:
(1 + 2 + 4 + (1 * 2) + (1 * 4) + (2 * 4) + (1 * 2 * 4)) = 29.
Enfoque ingenuo: el enfoque ingenuo para este problema es generar todos los subconjuntos posibles a partir de sus divisores y luego calcular el producto de cada uno de los subconjuntos. Después de calcular el producto de cada subconjunto, suma todos los productos para encontrar la respuesta requerida. La complejidad de tiempo para este enfoque es O(2 D ) donde D es el número de divisores de N.
Enfoque eficiente: La idea detrás del enfoque eficiente proviene de la siguiente observación:
Let x and y is the divisor of N. Then sum of product of all subsets will be = x + y + x * y = x(1 + y) + y + 1 - 1 = x(1 + y) + (1 + y) - 1 = (x + 1) * (y + 1) - 1 = (1 + x) * (1 + y) - 1 Now let take three divisors x, y, z. Then sum of product of all subsets will be = x + y + z + xy + yz + zx + xyz = x + xz + y + yz + xy + xyz + z + 1 - 1 = x(1 + z) + y(1 + z) + xy(1 + z) + z + 1 - 1 = (x + y + xy + 1) * (1 + z) - 1 = (1 + x) * (1 + y) * (1 + z) - 1
Claramente, de la observación anterior, podemos concluir que si {D 1 , D 2 , D 3 , … D n } son los divisores de N entonces la respuesta requerida será:
(D1 + 1) * (D2 + 1) * (D3 + 1) * ... (Dn + 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the sum of
// product of all the subsets
// formed by only divisors of N
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of
// product of all the subsets
// formed by only divisors of N
int GetSum(int n)
{
// Vector to store all the
// divisors of n
vector<int> divisors;
// Loop to find out the
// divisors of N
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
// Both 'i' and 'n/i' are the
// divisors of n
divisors.push_back(i);
// Check if 'i' and 'n/i' are
// equal or not
if (i != n / i) {
divisors.push_back(n / i);
}
}
}
int ans = 1;
// Calculating the answer
for (auto i : divisors) {
ans *= (i + 1);
}
// Excluding the value
// of the empty set
ans = ans - 1;
return ans;
}
// Driver Code
int main()
{
int N = 4;
cout << GetSum(N) << endl;
}
Java
// Java program to find the sum of product
// of all the subsets formed by only
// divisors of N
import java.util.*;
class GFG {
// Function to find the sum of product
// of all the subsets formed by only
// divisors of N
static int GetSum(int n)
{
// Vector to store all the
// divisors of n
Vector<Integer> divisors = new Vector<Integer>();
// Loop to find out the
// divisors of N
for(int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// Both 'i' and 'n/i' are the
// divisors of n
divisors.add(i);
// Check if 'i' and 'n/i' are
// equal or not
if (i != n / i)
{
divisors.add(n / i);
}
}
}
int ans = 1;
// Calculating the answer
for(int i = 0; i < divisors.size(); i++)
{
ans *= (divisors.get(i) + 1);
}
// Excluding the value
// of the empty set
ans = ans - 1;
return ans;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
System.out.println(GetSum(N));
}
}
// This code is contributed by offbeat
Python3
# Python3 program to find the sum of # product of all the subsets # formed by only divisors of N # Function to find the sum of # product of all the subsets # formed by only divisors of N def GetSum(n): # Vector to store all the # divisors of n divisors = [] # Loop to find out the # divisors of N i = 1 while i * i <= n : if (n % i == 0): # Both 'i' and 'n/i' are the # divisors of n divisors.append(i) # Check if 'i' and 'n/i' are # equal or not if (i != n // i): divisors.append(n // i) i += 1 ans = 1 # Calculating the answer for i in divisors: ans *= (i + 1) # Excluding the value # of the empty set ans = ans - 1 return ans # Driver Code if __name__ == "__main__": N = 4 print(GetSum(N)) # This code is contributed by chitranayal
C#
// C# program to find the sum of product
// of all the subsets formed by only
// divisors of N
using System;
using System.Collections.Generic;
class GFG{
// Function to find the sum of product
// of all the subsets formed by only
// divisors of N
static int GetSum(int n)
{
// Store all the
// divisors of n
List<int> divisors = new List<int>();
// Loop to find out the
// divisors of N
for(int i = 1; i * i <= n; i++)
{
if (n % i == 0)
{
// Both 'i' and 'n/i' are the
// divisors of n
divisors.Add(i);
// Check if 'i' and 'n/i' are
// equal or not
if (i != n / i)
{
divisors.Add(n / i);
}
}
}
int ans = 1;
// Calculating the answer
foreach(int i in divisors)
{
ans *= (i + 1);
}
// Excluding the value
// of the empty set
ans = ans - 1;
return ans;
}
// Driver code
public static void Main()
{
int N = 4;
Console.WriteLine(GetSum(N));
}
}
// This code is contributed by sanjoy_62
Javascript
<script>
// Javascript program to find the sum of
// product of all the subsets
// formed by only divisors of N
// Function to find the sum of
// product of all the subsets
// formed by only divisors of N
function GetSum(n)
{
// Vector to store all the
// divisors of n
var divisors = [];
// Loop to find out the
// divisors of N
for (var i = 1; i * i <= n; i++) {
if (n % i == 0) {
// Both 'i' and 'n/i' are the
// divisors of n
divisors.push(i);
// Check if 'i' and 'n/i' are
// equal or not
if (i != n / i) {
divisors.push(n / i);
}
}
}
var ans = 1;
// Calculating the answer
for(var i =0; i< divisors.length; i++)
{
ans *= (divisors[i]+1);
}
// Excluding the value
// of the empty set
ans = ans - 1;
return ans;
}
// Driver Code
var N = 4;
document.write( GetSum(N));
// This code is contributed by noob2000.
</script>
29
Complejidad de tiempo: O(sqrt(N)) , donde N es el número dado.
Espacio auxiliar: O(sqrt(N))