Dada una array arr[] que consta de N enteros positivos, la tarea es encontrar la suma de los factores del producto de todos los elementos de la array. Dado que la salida puede ser muy grande, imprímala módulo 10 9 + 7 .
Ejemplos:
Entrada: arr[] = { 1, 2, 3, 4, 5 }
Salida: 360
Explicación:
El producto de todos los elementos de la array = 1 * 2 * 3 * 4 * 5 = 120
Todos los factores de 120 son { 1, 2 , 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 }
Por lo tanto, la suma de factores es 360.Entrada: arr[] = { 1, 2 }
Salida: 3
Explicación:
El producto de todos los elementos de la array = 1 * 2 = 2
Todos los factores de 2 son { 1, 2 }
Por lo tanto, la suma de los factores es 3.
Enfoque ingenuo: el enfoque más simple para resolver este problema es atravesar la array y calcular el producto de todos los elementos de la array y calcular la suma de todos los factores del producto obtenido . Pero el problema con este enfoque es que, si los elementos de la array son grandes, entonces el producto puede salirse de los límites de la capacidad de almacenamiento de enteros y generará una salida incorrecta.
Complejidad de tiempo: O(max(N, sqrt(producto de los elementos de la array)))
Espacio auxiliar: O(N)
Enfoque eficiente: el enfoque anterior se puede optimizar en función de las siguientes observaciones:
Si el producto de los elementos del arreglo (P) =
Entonces, la suma de factores de P =
Siga los pasos a continuación para resolver el problema:
- Inicialice un número entero, digamos ans , para almacenar la suma de todos los factores del producto de la array.
- Inicialice una array de enteros, digamos count[] , donde count[i] almacena la frecuencia de los factores primos i , en producto de los elementos de la array.
- Recorra la array count[] y verifique si count[i] es mayor que cero o no. Si se determina que es cierto, multiplique ans por (i (count[i] + 1) ) – 1 y el inverso multiplicativo de (i -1)
- Finalmente, imprima el resultado obtenido en ans
A continuación se muestra la implementación del enfoque anterior:
C
// C program to implement
// the above approach
#include <stdio.h>
#define size 1000100
#define inverse(a) power(a, mod - 2)
typedef long long int ll;
const ll mod = ((ll)(1e9 + 7));
// Stores minimum prime
// factorization of a number
int spf[size] = { 0 };
// Function to add two numbers
static inline ll add(ll a, ll b)
{
return (a % mod + b % mod) % mod;
}
// Function to subtract two numbers
static inline ll sub(ll a, ll b)
{
return add(mod, a - b) % mod;
}
// Function to multiply two numbers
static inline ll mul(ll a, ll b)
{
return (a % mod * b % mod) % mod;
}
// Function to calculate
// x to the power y
ll power(ll x, ll y)
{
// Stores x ^ y
ll res = 1;
for (res = 1; y > 0;
x = (x * x) % mod, y >>= 1) {
// If y is odd
if (y & 1) {
// Update result
res = (res * x) % mod;
}
}
return res;
}
// Function to find the smallest prime factor
// of numbers in the range [1, 1000100]
void sieve()
{
// Update the smallest prime factor of
// all the numbers which is divisible by 2
for (int i = 2; i < size; i += 2) {
// Update spf[i]
spf[i] = 2;
}
for (int i = 3; i < size; i += 2)
spf[i] = i;
// Calculate the smallest prime factor
// of all the numbers in the range [3, 1000100]
for (int i = 3; i * i < size; i += 2)
if (spf[i] == i)
for (int j = i * i; j < size; j += i)
spf[j] = i;
}
// Function to find the sum of factors of
// product of all array elements
long long int sumof_factors(int a[], int n)
{
// Stores the sum of factors of
// product of all array elements
ll ans = 1;
// count[i]: Stores frequency of
// prime factor i in product of
// all the array elements
ll count[size] = { 0 };
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculate the prime factor
// of a[i]
while (a[i] > 1) {
// Update frequency of
// prime factor spf[a[i]]
count[spf[a[i]]]++;
// Update a[i]
a[i] /= spf[a[i]];
}
}
// Traverse the array, count[]
for (ll i = 0; i < size; i++)
// If frequency of prime factor i in
// product of array elements
// greater than 0
if (count[i] > 0) {
// Calculate (i^(count[i]+1))-1 and
// multiplicative inverse of (i -1)
ll num1 = sub(power(i, count[i] + 1), 1);
ll num2 = inverse(i - 1);
ans = mul(ans, mul(num1, num2));
}
return ans;
}
// Driver Code
int main()
{
sieve();
int arr[] = { 1, 3, 2, 5, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
ll res = sumof_factors(arr, N);
printf("%lld\n", res);
return 0;
}
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
#define size 1000100
#define inverse(a) power(a, mod - 2)
typedef long long int ll;
const ll mod = ((ll)(1e9 + 7));
// Stores minimum prime
// factorization of a number
int spf[size] = { 0 };
// Function to add two numbers
static inline ll add(ll a, ll b)
{
return (a % mod + b % mod) % mod;
}
// Function to subtract two numbers
static inline ll sub(ll a, ll b)
{
return add(mod, a - b) % mod;
}
// Function to multiply two numbers
static inline ll mul(ll a, ll b)
{
return (a % mod * b % mod) % mod;
}
// Function to calculate
// x to the power y
ll power(ll x, ll y)
{
// Stores x ^ y
ll res = 1;
for (res = 1; y > 0;
x = (x * x) % mod, y >>= 1) {
// If y is odd
if (y & 1) {
// Update result
res = (res * x) % mod;
}
}
return res;
}
// Function to find the smallest prime factor
// of numbers in the range [1, 1000100]
void sieve()
{
// Update the smallest prime factor of
// all the numbers which is divisible by 2
for (int i = 2; i < size; i += 2) {
// Update spf[i]
spf[i] = 2;
}
for (int i = 3; i < size; i += 2)
spf[i] = i;
// Calculate the smallest prime factor
// of all the numbers in the range [3, 1000100]
for (int i = 3; i * i < size; i += 2)
if (spf[i] == i)
for (int j = i * i; j < size; j += i)
spf[j] = i;
}
// Function to calculate sum of factors
// of product of the given array
long long int sumof_factors(int a[], int n)
{
// Stores the sum of factors of
// product of all array elements
ll ans = 1;
// count[i]: Stores frequency of
// prime factor i in product of
// all the array elements
ll count[size] = { 0 };
// Traverse the array
for (int i = 0; i < n; i++) {
// Calculate the prime factor
// of a[i]
while (a[i] > 1) {
// Update frequency of
// prime factor spf[a[i]]
count[spf[a[i]]]++;
// Update a[i]
a[i] /= spf[a[i]];
}
}
// Traverse the array, count[]
for (ll i = 0; i < size; i++)
// If frequency of prime factor i in
// product of array elements
// greater than 0
if (count[i] > 0) {
// Calculate (i^(count[i]+1))-1 and
// multiplicative inverse of (i -1)
ll num1 = sub(power(i, count[i] + 1), 1);
ll num2 = inverse(i - 1);
ans = mul(ans, mul(num1, num2));
}
return ans;
}
// Driver Code
int main()
{
sieve();
int arr[] = { 1, 3, 2, 5, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
ll res = sumof_factors(arr, N);
cout << res;
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.HashMap;
import java.util.Map;
class GFG {
static final long mod = (int)(1e9 + 7);
static final int size = (int)(1e6 + 100);
// Function to subtract two numbers
static final long sub(long a, long b)
{
return (mod + a % mod - b % mod) % mod;
}
// Function to multiply two numbers
static final long mul(long a, long b)
{
return (a % mod * b % mod) % mod;
}
// Function to calculate
// x to the power y
static long power(long x, long y)
{
// Stores x ^ y
long res = 1;
for (res = 1; y > 0;
x = (x * x) % mod, y >>= 1) {
// If y is odd
if ((y & 1) == 1) {
// Update result
res = (res * x) % mod;
}
}
return res;
}
// Function to find inverse
// of a mod 1e9 + 7
static long inverse(long a)
{
return power(a, mod - 2);
}
// Stores minimum prime
// factorization of a number
static int spf[] = new int[size];
// Function to find the smallest prime factor
// of numbers in the range [1, 1000100]
static void sieve()
{
for (int i = 1; i < size; i += 2)
spf[i] = i;
for (int i = 2; i < size; i += 2)
spf[i] = 2;
for (int i = 3; i * i < size; i += 2)
if (spf[i] == i)
for (int j = i * i; j < size; j += i)
spf[j] = i;
}
// Function to calculate sum of factors
// of product of the given array
static long sumof_factors(int a[], int n)
{
// Traverse the array
for (int i = 0; i < n; i++)
if (a[i] == 0)
return 0;
// Stores the sum of factors of
// product of all array elements
long ans = 1;
// count[i]: Stores frequency of
// prime factor i in product of
// all the array elements
Map<Integer, Integer> count
= new HashMap<Integer, Integer>();
// Traverse the array
for (int num : a) {
// Calculate the prime factor
// of a[i]
while (num > 1) {
int temp = 0;
try {
temp = count.get(spf[num]);
}
catch (Exception e) {
temp = 0;
}
// Update frequency of
// prime factor spf[a[i]]
count.put(spf[num], temp + 1);
// Update num
num /= spf[num];
}
}
for (Map.Entry<Integer, Integer> i :
count.entrySet()) {
// Calculate (i^(count[i]+1))-1 and
// multiplicative inverse of (i -1)
long num1 = sub(
power(i.getKey(), i.getValue() + 1), 1);
long num2 = inverse(i.getKey() - 1);
ans = mul(ans, mul(num1, num2));
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
sieve();
int n = 5;
int a[] = { 1, 3, 2, 5, 4 };
System.out.println(sumof_factors(a, n));
}
}
Python3
# Python program to implement # the above approach from collections import defaultdict from math import sqrt # Function to find the smallest prime factor # of numbers in the range [1, 1000100] def computeSPF(size): # Stores smallest prime # factorization of a number spf = [i for i in range(size)] # Update the smallest prime factor of # all the numbers which is divisible by 2 for i in range(2, size, 2): spf[i] = 2 # Calculate the smallest prime factor # of all the numbers in the range [3, 1000100] for i in range(3, int(sqrt(size))+1, 2): if spf[i] == i: for j in range(i * i, size, i): spf[j] = i return spf # Function to calculate sum of factors # of product of the given array def sumof_factors(a, n, spf, mod): # Traverse the array if 0 in a: return 0 count = defaultdict(int) # Stores the sum of factors of # product of all array elements ans = 1 # Traverse the array for num in a: # Calculate the prime factor # of a[i] while num > 1: # Update frequency of # prime factor spf[a[i]] count[spf[num]] += 1 num //= spf[num] # Traverse the array, count[] for i in count: num1 = pow(i, count[i]+1, mod) - 1 num2 = pow(i-1, mod-2, mod) ans = (ans * num1 * num2) % mod return ans # Driver Code def main(): spf = computeSPF(10**6) mod = 10**9 + 7 n = 4 a = [1, 3, 2, 5] ans = sumof_factors(a, n, spf, mod) print(ans) main()
C#
// C# program to implement
// the above approach
using System;
using System.Collections.Generic;
class GFG {
static long mod = (int)(1e9 + 7);
static int size = (int)(1e6 + 100);
// Function to subtract two numbers
static long sub(long a, long b)
{
return (mod + a % mod - b % mod) % mod;
}
// Function to multiply two numbers
static long mul(long a, long b)
{
return (a % mod * b % mod) % mod;
}
// Function to calculate
// x to the power y
static long power(long x, long y)
{
// Stores x ^ y
long res = 1;
for (res = 1; y > 0; x = (x * x) % mod, y >>= 1) {
// If y is odd
if ((y & 1) == 1) {
// Update result
res = (res * x) % mod;
}
}
return res;
}
// Function to find inverse
// of a mod 1e9 + 7
static long inverse(long a)
{
return power(a, mod - 2);
}
// Stores minimum prime
// factorization of a number
static int[] spf = new int[size];
// Function to find the smallest prime factor
// of numbers in the range [1, 1000100]
static void sieve()
{
for (int i = 1; i < size; i += 2)
spf[i] = i;
for (int i = 2; i < size; i += 2)
spf[i] = 2;
for (int i = 3; i * i < size; i += 2)
if (spf[i] == i)
for (int j = i * i; j < size; j += i)
spf[j] = i;
}
// Function to calculate sum of factors
// of product of the given array
static long sumof_factors(int[] a, int n)
{
// Traverse the array
for (int i = 0; i < n; i++)
if (a[i] == 0)
return 0;
// Stores the sum of factors of
// product of all array elements
long ans = 1;
// count[i]: Stores frequency of
// prime factor i in product of
// all the array elements
Dictionary<int, int> count
= new Dictionary<int, int>();
// Traverse the array
for (int i = 0; i < a.Length; i++) {
// Calculate the prime factor
// of a[i]
while (a[i] > 1) {
int temp = 0;
if (count.ContainsKey(spf[a[i]]))
temp = count[spf[a[i]]];
// Update frequency of
// prime factor spf[a[i]]
count[spf[a[i]]] = temp + 1;
// Update num
a[i] /= spf[a[i]];
}
}
foreach(KeyValuePair<int, int> i in count)
{
// Calculate (i^(count[i]+1))-1 and
// multiplicative inverse of (i -1)
long num1 = sub(power(i.Key, i.Value + 1), 1);
long num2 = inverse(i.Key - 1);
ans = mul(ans, mul(num1, num2));
}
return ans;
}
// Driver Code
public static void Main(string[] args)
{
sieve();
int n = 5;
int[] a = { 1, 3, 2, 5, 4 };
Console.WriteLine(sumof_factors(a, n));
}
}
// This code is contributed by ukasp.
Producción:
360
Complejidad de tiempo: O(N * log(log(N)))
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por suman_1729 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA