Dada una array arr[] que representa una lista de factores primos de un número dado, la tarea es encontrar el producto de los divisores de ese número.
Nota: Dado que el producto puede tener una impresión muy grande, la respuesta es mod 10 9 + 7.
Ejemplos:
Entrada: arr[] = {2, 2, 3}
Salida: 1728
Explicación:
Producto de los factores primos dados = 2 * 2 * 3 = 12.
Los divisores de 12 son {1, 2, 3, 4, 6, 12} .
Por lo tanto, el producto de divisores es 1728.Entrada: arr[] = {11, 11}
Salida: 1331
Enfoque ingenuo:
genere el número N a partir de su lista de factores primos, luego encuentre todos sus divisores en la complejidad computacional O(√N) y siga calculando su producto. Imprimir el producto final obtenido.
Complejidad Temporal: O(N 3/2 )
Espacio Auxiliar: O(1)
Enfoque Eficiente:
Para resolver el problema se deben tener en cuenta las siguientes observaciones:
- De acuerdo con el pequeño teorema de Fermat , a (m – 1) = 1 (mod m) que se puede extender a x = a x % (m – 1) (mod m)
- Para un primo p elevado a la potencia a , f(p a ) = p (a * (a + 1) / 2)) .
- Por lo tanto, f(a * b) = f(a) (d(b)) * f(b) (d(a)) , donde d(a), d(b) denota el número de divisores en a y b respectivamente.
Siga los pasos a continuación para resolver el problema:
- Encuentre la frecuencia de cada primo en la lista dada (usando un HashMap / Dictionary ).
- Usando la segunda observación, para cada i -ésimo primo, calcule:
fp = power(p[i], (cnt[i] + 1) * cnt[i] / 2), donde cnt[i] denota la frecuencia de ese primo
- Usando la tercera observación, actualice el producto requerido:
ans = power(ans, (cnt[i] + 1)) * power(fp, d) % MOD, donde d es el número de divisores hasta (i – 1) th primo
- El número de divisores d se actualiza usando el Pequeño Teorema de Fermat:
d = d * (cnt[i] + 1) % (MOD – 1)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; int MOD = 1000000007; // Function to calculate (a^b)% m int power(int a, int b, int m) { a %= m; int res = 1; while (b > 0) { if (b & 1) res = ((res % m) * (a % m)) % m; a = ((a % m) * (a % m)) % m; b >>= 1; } return res % m; } // Function to calculate and return // the product of divisors int productOfDivisors(int p[], int n) { // Stores the frequencies of // prime divisors map<int, int> prime; for (int i = 0; i < n; i++) { prime[p[i]]++; } int product = 1, d = 1; // Iterate over the prime // divisors for (auto itr : prime) { int val = power(itr.first, (itr.second) * (itr.second + 1) / 2, MOD); // Update the product product = (power(product, itr.second + 1, MOD) * power(val, d, MOD)) % MOD; // Update the count of divisors d = (d * (itr.second + 1)) % (MOD - 1); } return product; } // Driver Code int main() { int arr[] = { 11, 11 }; int n = sizeof(arr) / sizeof(arr[0]); cout <<productOfDivisors(arr,n); }
Java
// Java Program to implement // the above approach import java.util.*; class GFG{ static int MOD = 1000000007; // Function to calculate (a^b)% m static int power(int a, int b, int m) { a %= m; int res = 1; while (b > 0) { if (b % 2 == 1) res = ((res % m) * (a % m)) % m; a = ((a % m) * (a % m)) % m; b >>= 1; } return res % m; } // Function to calculate and return // the product of divisors static int productOfDivisors(int p[], int n) { // Stores the frequencies of // prime divisors HashMap<Integer, Integer> prime = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { if(prime.containsKey(p[i])) prime.put(p[i], prime.get(p[i]) + 1); else prime.put(p[i], 1); } int product = 1, d = 1; // Iterate over the prime // divisors for (Map.Entry<Integer, Integer> itr : prime.entrySet()) { int val = power(itr.getKey(), (itr.getValue()) * (itr.getValue() + 1) / 2, MOD); // Update the product product = (power(product, itr.getValue() + 1, MOD) * power(val, d, MOD)) % MOD; // Update the count of divisors d = (d * (itr.getValue() + 1)) % (MOD - 1); } return product; } // Driver Code public static void main(String[] args) { int arr[] = { 11, 11 }; int n = arr.length; System.out.println(productOfDivisors(arr,n)); } } // This code is contributed by sapnasingh4991
Python3
# Python3 program to implement # the above approach from collections import defaultdict MOD = 1000000007 # Function to calculate (a^b)% m def power(a, b, m): a %= m res = 1 while (b > 0): if (b & 1): res = ((res % m) * (a % m)) % m a = ((a % m) * (a % m)) % m b >>= 1 return res % m # Function to calculate and return # the product of divisors def productOfDivisors(p, n): # Stores the frequencies of # prime divisors prime = defaultdict(int) for i in range(n): prime[p[i]] += 1 product, d = 1, 1 # Iterate over the prime # divisors for itr in prime.keys(): val = (power(itr, (prime[itr]) * (prime[itr] + 1) // 2, MOD)) # Update the product product = (power(product, prime[itr] + 1, MOD) * power(val, d, MOD) % MOD) # Update the count of divisors d = (d * (prime[itr] + 1)) % (MOD - 1) return product # Driver Code if __name__ == "__main__": arr = [ 11, 11 ] n = len(arr) print(productOfDivisors(arr, n)) # This code is contributed by chitranayal
C#
// C# program to implement // the above approach using System; using System.Collections.Generic; class GFG{ static int MOD = 1000000007; // Function to calculate (a^b)% m static int power(int a, int b, int m) { a %= m; int res = 1; while (b > 0) { if (b % 2 == 1) res = ((res % m) * (a % m)) % m; a = ((a % m) * (a % m)) % m; b >>= 1; } return res % m; } // Function to calculate and return // the product of divisors static int productOfDivisors(int []p, int n) { // Stores the frequencies of // prime divisors Dictionary<int, int> prime = new Dictionary<int, int>(); for(int i = 0; i < n; i++) { if(prime.ContainsKey(p[i])) prime[p[i]] = prime[p[i]] + 1; else prime.Add(p[i], 1); } int product = 1, d = 1; // Iterate over the prime // divisors foreach(KeyValuePair<int, int> itr in prime) { int val = power(itr.Key, (itr.Value) * (itr.Value + 1) / 2, MOD); // Update the product product = (power(product, itr.Value + 1, MOD) * power(val, d, MOD)) % MOD; // Update the count of divisors d = (d * (itr.Value + 1)) % (MOD - 1); } return product; } // Driver Code public static void Main(String[] args) { int []arr = { 11, 11 }; int n = arr.Length; Console.WriteLine(productOfDivisors(arr,n)); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // Javascript Program to implement // the above approach var MOD = 1000000007; // Function to calculate (a^b)% m function power(a, b, m) { a %= m; var res = 1; while (b > 0) { if (b & 1) res = ((res % m) * (a % m)) % m; a = ((a % m) * (a % m)) % m; b >>= 1; } return res % m; } // Function to calculate and return // the product of divisors function productOfDivisors(p, n) { // Stores the frequencies of // prime divisors var prime = new Map(); for (var i = 0; i < n; i++) { if(prime.has(p[i])) prime.set(p[i], prime.get(p[i])+1) else prime.set(p[i],1) } var product = 1, d = 1; // Iterate over the prime // divisors prime.forEach((value, key) => { var val = power(key, (value) * (value + 1) / 2, MOD); // Update the product product = (power(product, value + 1, MOD) * power(val, d, MOD)) % MOD; // Update the count of divisors d = (d * (value + 1)) % (MOD - 1); }); return product; } // Driver Code var arr = [11, 11]; var n = arr.length; document.write( productOfDivisors(arr,n)); </script>
1331
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por debargham14 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA