Dada una array arr[] de enteros de tamaño n . Para cada elemento, debe imprimir la suma de la multiplicación de cada triplete formado usando divisores de este elemento.
Ejemplos:
Entrada: arr[] = {4}
Salida: 8
4 tiene tres divisores 1, 2 y 4.
1 * 2 * 4 = 8
Entrada: arr[] = {9, 5, 6}
Salida: 27 0 72
9 tiene tres divisores 1, 3 y 9. 1 * 3 * 9 = 27
5 tiene dos divisores 1 y 5. Entonces, no se forma ningún triplete.
Del mismo modo, 6 tiene cuatro divisores 1, 2, 3 y 6. (1 * 2 * 3) + (1 * 3 * 6) + (2 * 3 * 6) + (1 * 6 * 2) = 72
Enfoque ingenuo: almacene todos los divisores de un número y aplique el método de fuerza bruta y para cada triplete, agregue la multiplicación de estos tres elementos a la respuesta.
Enfoque eficiente: este método es similar a la criba de Eratóstenes , que usamos para encontrar todos los números primos de un rango.
- Primero, creamos una array sum1 que almacena la suma de todos los divisores del número x en sum1[x]. Así que primero recorre todos los números menores que el elemento_máximo y suma este número a la suma de los divisores de los múltiplos de este número. Por lo tanto, podremos almacenar la suma de todos los divisores de cualquier número en la posición de ese número.
- Después de llenar la array sum1, es hora de llenar la segunda array sum2 que almacenará la suma de la multiplicación de cada par divisor del número x en sum2[x]. Para llenar esto, buscamos cada número similar al paso 1 y sumamos la multiplicación de este número con sus valores más altos.
- Para llenar la array sum3, iremos de manera similar para todos los números menores que max_Element y agregaremos la suma de la multiplicación de los divisores de j de modo que i sea un divisor de j.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll max_Element = 1e6 + 5;
// Global array declaration
int sum1[max_Element], sum2[max_Element], sum3[max_Element];
// Function to find the sum of multiplication of
// every triplet in the divisors of a number
void precomputation(int arr[], int n)
{
// sum1[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Adding i to sum1[j] because i
// is a divisor of j
sum1[j] += i;
// sum2[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Here i is divisor of j and sum1[j] - i
// represents sum of all divisors of
// j which do not include i so we add
// i * (sum1[j] - i) to sum2[j]
sum2[j] += (sum1[j] - i) * i;
// In the above implementation we have considered
// every pair two times so we have to divide
// every sum2 array element by 2
for (int i = 1; i < max_Element; i++)
sum2[i] /= 2;
// Here i is the divisor of j and we are trying to
// add the sum of multiplication of all triplets of
// divisors of j such that one of the divisors is i
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
sum3[j] += i * (sum2[j] - i * (sum1[j] - i));
// In the above implementation we have considered
// every triplet three times so we have to divide
// every sum3 array element by 3
for (int i = 1; i < max_Element; i++)
sum3[i] /= 3;
// Print the results
for (int i = 0; i < n; i++)
cout << sum3[arr[i]] << " ";
}
// Driver code
int main()
{
int arr[] = { 9, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
// Precomputing
precomputation(arr, n);
return 0;
}
Java
// Java implementation of the approach
class GFGq
{
static int max_Element = (int) (1e6 + 5);
// Global array declaration
static int sum1[] = new int[max_Element], sum2[] =
new int[max_Element], sum3[] = new int[max_Element];
// Function to find the sum of multiplication of
// every triplet in the divisors of a number
static void precomputation(int arr[], int n)
{
// sum1[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Adding i to sum1[j] because i
// is a divisor of j
sum1[j] += i;
// sum2[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Here i is divisor of j and sum1[j] - i
// represents sum of all divisors of
// j which do not include i so we add
// i * (sum1[j] - i) to sum2[j]
sum2[j] += (sum1[j] - i) * i;
// In the above implementation we have considered
// every pair two times so we have to divide
// every sum2 array element by 2
for (int i = 1; i < max_Element; i++)
sum2[i] /= 2;
// Here i is the divisor of j and we are trying to
// add the sum of multiplication of all triplets of
// divisors of j such that one of the divisors is i
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
sum3[j] += i * (sum2[j] - i * (sum1[j] - i));
// In the above implementation we have considered
// every triplet three times so we have to divide
// every sum3 array element by 3
for (int i = 1; i < max_Element; i++)
sum3[i] /= 3;
// Print the results
for (int i = 0; i < n; i++)
System.out.print(sum3[arr[i]] + " ");
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 9, 5, 6 };
int n = arr.length;
// Precomputing
precomputation(arr, n);
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python 3 implementation of the approach # Global array declaration #global max_Element max_Element = 100005 sum1 = [0 for i in range(max_Element)] sum2 = [0 for i in range(max_Element)] sum3 = [0 for i in range(max_Element)] # Function to find the sum of multiplication of # every triplet in the divisors of a number def precomputation(arr, n): # global max_Element # sum1[x] represents the sum of # all the divisors of x for i in range(1, max_Element, 1): for j in range(i, max_Element, i): # Adding i to sum1[j] because i # is a divisor of j sum1[j] += i # sum2[x] represents the sum of # all the divisors of x for i in range(1, max_Element, 1): for j in range(i, max_Element, i): # Here i is divisor of j and sum1[j] - i # represents sum of all divisors of # j which do not include i so we add # i * (sum1[j] - i) to sum2[j] sum2[j] += (sum1[j] - i) * i # In the above implementation we have considered # every pair two times so we have to divide # every sum2 array element by 2 for i in range(1, max_Element, 1): sum2[i] = int(sum2[i] / 2) # Here i is the divisor of j and we are trying to # add the sum of multiplication of all triplets of # divisors of j such that one of the divisors is i for i in range(1, max_Element, 1): for j in range(i, max_Element, i): sum3[j] += i * (sum2[j] - i * (sum1[j] - i)) # In the above implementation we have considered # every triplet three times so we have to divide # every sum3 array element by 3 for i in range(1, max_Element, 1): sum3[i] = int(sum3[i] / 3) # Print the results for i in range(n): print(sum3[arr[i]], end = " ") # Driver code if __name__ == '__main__': arr = [9, 5, 6] n = len(arr) # Precomputing precomputation(arr, n) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the approach
using System;
class GFG
{
static int max_Element = (int) (1e6 + 5);
// Global array declaration
static int []sum1 = new int[max_Element];
static int []sum2 = new int[max_Element];
static int []sum3 = new int[max_Element];
// Function to find the sum of multiplication of
// every triplet in the divisors of a number
static void precomputation(int []arr, int n)
{
// sum1[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Adding i to sum1[j] because i
// is a divisor of j
sum1[j] += i;
// sum2[x] represents the sum of all the divisors of x
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
// Here i is divisor of j and sum1[j] - i
// represents sum of all divisors of
// j which do not include i so we add
// i * (sum1[j] - i) to sum2[j]
sum2[j] += (sum1[j] - i) * i;
// In the above implementation we have considered
// every pair two times so we have to divide
// every sum2 array element by 2
for (int i = 1; i < max_Element; i++)
sum2[i] /= 2;
// Here i is the divisor of j and we are trying to
// add the sum of multiplication of all triplets of
// divisors of j such that one of the divisors is i
for (int i = 1; i < max_Element; i++)
for (int j = i; j < max_Element; j += i)
sum3[j] += i * (sum2[j] - i * (sum1[j] - i));
// In the above implementation we have considered
// every triplet three times so we have to divide
// every sum3 array element by 3
for (int i = 1; i < max_Element; i++)
sum3[i] /= 3;
// Print the results
for (int i = 0; i < n; i++)
Console.Write(sum3[arr[i]] + " ");
}
// Driver code
public static void Main()
{
int []arr = { 9, 5, 6 };
int n = arr.Length;
// Precomputing
precomputation(arr, n);
}
}
// This code has been contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
$max_Element = 1005;
// Global array declaration
$sum1 = array_fill(0, $max_Element, 0);
$sum2 = array_fill(0, $max_Element, 0);
$sum3 = array_fill(0, $max_Element, 0);
// Function to find the sum of multiplication of
// every triplet in the divisors of a number
function precomputation($arr, $n)
{
global $max_Element, $sum3, $sum2, $sum1;
// sum1[x] represents the sum of
// all the divisors of x
for ($i = 1; $i < $max_Element; $i++)
for ($j = $i; $j < $max_Element; $j += $i)
// Adding i to sum1[j] because i
// is a divisor of j
$sum1[$j] += $i;
// sum2[x] represents the sum of
// all the divisors of x
for ($i = 1; $i < $max_Element; $i++)
for ($j = $i; $j < $max_Element; $j += $i)
// Here i is divisor of j and sum1[j] - i
// represents sum of all divisors of
// j which do not include i so we add
// i * (sum1[j] - i) to sum2[j]
$sum2[$j] += ($sum1[$j] - $i) * $i;
// In the above implementation we have considered
// every pair two times so we have to divide
// every sum2 array element by 2
for ($i = 1; $i < $max_Element; $i++)
$sum2[$i] = (int)($sum2[$i] / 2);
// Here i is the divisor of j and we are trying to
// add the sum of multiplication of all triplets of
// divisors of j such that one of the divisors is i
for ($i = 1; $i < $max_Element; $i++)
for ($j = $i; $j < $max_Element; $j += $i)
$sum3[$j] += $i * ($sum2[$j] - $i *
($sum1[$j] - $i));
// In the above implementation we have considered
// every triplet three times so we have to divide
// every sum3 array element by 3
for ($i = 1; $i < $max_Element; $i++)
$sum3[$i] = (int)($sum3[$i] / 3);
// Print the results
for ($i = 0; $i < $n; $i++)
echo $sum3[$arr[$i]] . " ";
}
// Driver code
$arr = array( 9, 5, 6 );
$n = count($arr);
// Precomputing
precomputation($arr, $n);
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript implementation of the approach
var max_Element = 1e6 + 5;
// Global array declaration
var sum1=new Array(max_Element).fill(0);
var sum2=new Array(max_Element).fill(0);
var sum3=new Array(max_Element).fill(0);
// Function to find the sum of multiplication of
// every triplet in the divisors of a number
function precomputation( arr, n)
{
// sum1[x] represents the sum of all the divisors of x
for (var i = 1; i < max_Element; i++)
for (var j = i; j < max_Element; j += i)
// Adding i to sum1[j] because i
// is a divisor of j
sum1[j] += i;
// sum2[x] represents the sum of all the divisors of x
for (var i = 1; i < max_Element; i++)
for (var j = i; j < max_Element; j += i)
// Here i is divisor of j and sum1[j] - i
// represents sum of all divisors of
// j which do not include i so we add
// i * (sum1[j] - i) to sum2[j]
sum2[j] += (sum1[j] - i) * i;
// In the above implementation we have considered
// every pair two times so we have to divide
// every sum2 array element by 2
for (var i = 1; i < max_Element; i++)
sum2[i] /= 2;
// Here i is the divisor of j and we are trying to
// add the sum of multiplication of all triplets of
// divisors of j such that one of the divisors is i
for (var i = 1; i < max_Element; i++)
for (var j = i; j < max_Element; j += i)
sum3[j] += i * (sum2[j] - i * (sum1[j] - i));
// In the above implementation we have considered
// every triplet three times so we have to divide
// every sum3 array element by 3
for (var i = 1; i < max_Element; i++)
sum3[i] /= 3;
// Print the results
for (var i = 0; i < n; i++)
document.write( sum3[arr[i]] + " ");
}
var arr=[9, 5, 6 ];
var n =3;
// Precomputing
precomputation(arr, n);
</script>
Producción:
27 0 72
Complejidad del tiempo: O(max 2 )
Espacio auxiliar: O(max)
Publicación traducida automáticamente
Artículo escrito por saurabh_mittal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA