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>
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