Given an array arr[] representing a list of prime factors of a given number, the task is to find the product of divisors of that number.
Note: Since the product can be, very large printed, the answer is mod 109 + 7.
Examples:
Input: arr[] = {2, 2, 3}
Output: 1728
Explanation:
Product of the given prime factors = 2 * 2 * 3 = 12.
Divisors of 12 are {1, 2, 3, 4, 6, 12}.
Hence, the product of divisors is 1728.Input: arr[] = {11, 11}
Output: 1331
Naive Approach:
Generate the number N from its list of prime factors, then find all its divisors in O(?N) computational complexity and keep computing their product. Print the final product obtained.
Time Complexity: O(N3/2)
Auxiliary Space: O(1)
Efficient Approach:
To solve the problem, the following observations need to be taken into account:
- According to Fermat’s little theorem, a(m – 1) = 1 (mod m) which can be further extended to ax = a x % (m – 1) (mod m)
- For a prime p raised to the power a, f(pa) = p(a * (a + 1) / 2)).
- Hence, f(a * b) = f(a)(d(b)) * f(b)(d(a)), where d(a), d(b) denotes the number of divisors in a and b respectively.
Follow the steps below to solve the problem:
- Find the frequency of every prime in the given list (using a HashMap/Dictionary).
- Using the second observation, for every ith prime, calculate:
fp = power(p[i], (cnt[i] + 1) * cnt[i] / 2), where cnt[i] denotes the frequency of that prime
- Using the third observation, update the required product:
ans = power(ans, (cnt[i] + 1)) * power(fp, d) % MOD, where d is the number of divisors up to (i – 1)th prime
- The number of divisors d is updated using Fermat’s Little Theorem:
d = d * (cnt[i] + 1) % (MOD – 1)
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h> using namespace std;int MOD = 1000000007;// Function to calculate (a^b)% mint 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 divisorsint 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 Codeint main(){ int arr[] = { 11, 11 }; int n = sizeof(arr) / sizeof(arr[0]); cout <<productOfDivisors(arr,n); } |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{static int MOD = 1000000007;// Function to calculate (a^b)% mstatic 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 divisorsstatic 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 Codepublic 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 defaultdictMOD = 1000000007# Function to calculate (a^b)% mdef 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 divisorsdef 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 Codeif __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 approachusing System;using System.Collections.Generic;class GFG{static int MOD = 1000000007; // Function to calculate (a^b)% mstatic 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 divisorsstatic 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 Codepublic 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 approachvar MOD = 1000000007;// Function to calculate (a^b)% mfunction 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 divisorsfunction 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 Codevar arr = [11, 11];var n = arr.length;document.write( productOfDivisors(arr,n));</script> |
Output:
1331
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
