Given an integer N, the task is to find the product of proper divisors of the number modulo 109 + 7 for Q queries.
Examples:
Input: Q = 4, arr[] = { 4, 6, 8, 16 };
Output: 2 6 8 64
Explanation:
4 => 1, 2 = 1 * 2 = 2
6 => 1, 2, 3 = 1 * 2 * 3 = 6
8 => 1, 2, 4 = 1 * 2 * 4 = 8
16 => 1, 2, 4, 8 = 1 * 2 * 4 * 8 = 64Input: arr[] = { 3, 6, 9, 12 }
Output: 1 6 3 144
Approach: The idea is to pre-compute and store product of proper divisors of elements with the help of Sieve of Eratosthenes.
Below is the implementation of the above approach:
C++
// C++ implementation of// the above approach#include <bits/stdc++.h>#define ll long long int#define mod 1000000007using namespace std;vector<ll> ans(100002, 1);// Function to precompute the product// of proper divisors of a number at// it's corresponding indexvoid preCompute(){ for (int i = 2; i <= 100000 / 2; i++) { for (int j = 2 * i; j <= 100000; j += i) { ans[j] = (ans[j] * i) % mod; } }}int productOfProperDivi(int num){ // Returning the pre-computed // values return ans[num];}// Driver codeint main(){ preCompute(); int queries = 5; int a[queries] = { 4, 6, 8, 16, 36 }; for (int i = 0; i < queries; i++) { cout << productOfProperDivi(a[i]) << ", "; } return 0;} |
Java
// Java implementation of// the above approachimport java.util.*;class GFG{ static final int mod = 1000000007; static long[] ans = new long[100002]; // Function to precompute the product // of proper divisors of a number at // it's corresponding index static void preCompute() { for (int i = 2; i <= 100000 / 2; i++) { for (int j = 2 * i; j <= 100000; j += i) { ans[j] = (ans[j] * i) % mod; } } } static long productOfProperDivi(int num) { // Returning the pre-computed // values return ans[num]; } // Driver code public static void main(String[] args) { Arrays.fill(ans, 1); preCompute(); int queries = 5; int[] a = { 4, 6, 8, 16, 36 }; for (int i = 0; i < queries; i++) { System.out.print(productOfProperDivi(a[i]) + ", "); } }}// This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of# the above approachmod = 1000000007ans = [1] * (100002)# Function to precompute the product# of proper divisors of a number at# it's corresponding indexdef preCompute(): for i in range(2, 100000 // 2 + 1): for j in range(2 * i, 100001, i): ans[j] = (ans[j] * i) % moddef productOfProperDivi(num): # Returning the pre-computed # values return ans[num]# Driver codeif __name__ == "__main__": preCompute() queries = 5 a = [ 4, 6, 8, 16, 36 ] for i in range(queries): print(productOfProperDivi(a[i]), end = ", ")# This code is contributed by chitranayal |
C#
// C# implementation of// the above approachusing System;class GFG{ static readonly int mod = 1000000007;static long[] ans = new long[100002];// Function to precompute the product// of proper divisors of a number at// it's corresponding indexstatic void preCompute(){ for(int i = 2; i <= 100000 / 2; i++) { for(int j = 2 * i; j <= 100000; j += i) { ans[j] = (ans[j] * i) % mod; } }}static long productOfProperDivi(int num){ // Returning the pre-computed // values return ans[num];}// Driver codepublic static void Main(String[] args){ for(int i = 0 ; i < 100002; i++) ans[i] = 1; preCompute(); int queries = 5; int[] a = { 4, 6, 8, 16, 36 }; for(int i = 0; i < queries; i++) { Console.Write(productOfProperDivi(a[i]) + ", "); }}}// This code is contributed by Princi Singh |
Javascript
<script>// Javascript implementation of// the above approachmod = 1000000007ans = Array(100002).fill(1)// Function to precompute the product// of proper divisors of a number at// it's corresponding indexfunction preCompute(){ for (var i = 2; i <= 100000 / 2; i++) { for (var j = 2 * i; j <= 100000; j += i) { ans[j] = (ans[j] * i) % mod; } }}function productOfProperDivi(num){ // Returning the pre-computed // values return ans[num];}// Driver codepreCompute();var queries = 5;var a = [ 4, 6, 8, 16, 36 ];for (var i = 0; i < queries; i++) { document.write( productOfProperDivi(a[i]) + ", ");}</script> |
Output
2, 6, 8, 64, 279936,
Using Sieve of Eratosthenes:
Approach:
We can use the Sieve of Eratosthenes algorithm to precompute all the divisors of a number and then use them to compute the product of proper divisors. We can store the computed values in an array to reduce the time complexity of subsequent queries.
We first create a function sieve_of_eratosthenes that generates a list of divisors for each number from 1 to n using the Sieve of Eratosthenes algorithm. This function has a time complexity of O(N log N) and a space complexity of O(NM), where N is the maximum value in the input array, and M is the maximum number of divisors a number in the input array can have.
We create another function product_of_proper_divisors that takes an input array arr and the number of queries Q. For each query, we first find the divisors of the given number using the divisors list generated by the sieve_of_eratosthenes function. We then compute the product of all divisors except for the number itself. Finally, we print the product. The time complexity of this function is O(QM), where M is the maximum number of divisors a number in the input array can have.
We create two examples of input arrays arr, and we call the product_of_proper_divisors function for each of them. We print the input and output for each example.
C++
#include <iostream>#include <vector>#include <algorithm>using namespace std;// Function to generate all divisors of numbers // up to n using the Sieve of Eratosthenesvector<vector<int>> sieve_of_eratosthenes(int n) { vector<vector<int>> divisors(n+1); for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { divisors[j].push_back(i); } } return divisors;}// Function to calculate the product of // all proper divisors of each number in arrvoid product_of_proper_divisors(int arr[], int Q){ // Generate all divisors up to the maximum number in arr vector<vector<int>> divisors = sieve_of_eratosthenes(*max_element(arr, arr+Q)); // Calculate the product of all proper divisors for each number in arr for (int i = 0; i < Q; i++) { int n = arr[i]; int product = 1; // Multiply all divisors except for the number itself for (int j = 0; j < divisors[n].size()-1; j++) { product *= divisors[n][j]; } cout << product << endl; }}int main() { int arr[] = {4, 6, 8, 16}; int Q = sizeof(arr) / sizeof(arr[0]); cout << "Input: Q = " << Q << ", arr[] = {"; for (int i = 0; i < Q-1; i++) { cout << arr[i] << ", "; } cout << arr[Q-1] << "}" << endl; cout << "Output:" << endl; product_of_proper_divisors(arr, Q); int arr2[] = {3, 6, 9, 12}; Q = sizeof(arr2) / sizeof(arr2[0]); cout << "Input: Q = " << Q << ", arr[] = {"; for (int i = 0; i < Q-1; i++) { cout << arr2[i] << ", "; } cout << arr2[Q-1] << "}" << endl; cout << "Output:" << endl; product_of_proper_divisors(arr2, Q); return 0;} |
Java
// Java code for the given approachimport java.util.*;public class Main { // Function to generate all divisors of numbers // up to n using the Sieve of Eratosthenes static List<List<Integer>> sieve_of_eratosthenes(int n) { List<List<Integer>> divisors = new ArrayList<>(); for (int i = 0; i <= n; i++) { divisors.add(new ArrayList<Integer>()); } for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { divisors.get(j).add(i); } } return divisors; } // Function to calculate the product of // all proper divisors of each number in arr static void product_of_proper_divisors(int[] arr, int Q) { // Generate all divisors up to the maximum number in arr List<List<Integer>> divisors = sieve_of_eratosthenes(Arrays.stream(arr).max().getAsInt()); // Calculate the product of all proper divisors for each number in arr for (int i = 0; i < Q; i++) { int n = arr[i]; int product = 1; // Multiply all divisors except for the number itself for (int j = 0; j < divisors.get(n).size()-1; j++) { product *= divisors.get(n).get(j); } System.out.println(product); } } public static void main(String[] args) { int[] arr = {4, 6, 8, 16}; int Q = arr.length; System.out.print("Input: Q = " + Q + ", arr[] = {"); for (int i = 0; i < Q-1; i++) { System.out.print(arr[i] + ", "); } System.out.println(arr[Q-1] + "}"); System.out.println("Output:"); product_of_proper_divisors(arr, Q); int[] arr2 = {3, 6, 9, 12}; Q = arr2.length; System.out.print("Input: Q = " + Q + ", arr[] = {"); for (int i = 0; i < Q-1; i++) { System.out.print(arr2[i] + ", "); } System.out.println(arr2[Q-1] + "}"); System.out.println("Output:"); product_of_proper_divisors(arr2, Q); }}// This code is contributed by Utkarsh |
Python3
def sieve_of_eratosthenes(n): divisors = [[] for i in range(n+1)] for i in range(1, n+1): for j in range(i, n+1, i): divisors[j].append(i) return divisorsdef product_of_proper_divisors(arr, Q): divisors = sieve_of_eratosthenes(max(arr)) for i in range(Q): n = arr[i] product = 1 for divisor in divisors[n][:-1]: product *= divisor print(product)# Example usagearr = [4, 6, 8, 16]Q = len(arr)print("Input: Q =", Q, "arr[] =", arr)print("Output:")product_of_proper_divisors(arr, Q)arr = [3, 6, 9, 12]Q = len(arr)print("Input: Q =", Q, "arr[] =", arr)print("Output:")product_of_proper_divisors(arr, Q) |
C#
// C# code for the given approachusing System;using System.Collections.Generic;using System.Linq;public class GFG{ // Function to generate all divisors of numbers // up to n using the Sieve of Eratosthenes static List<List<int>> sieve_of_eratosthenes(int n) { List<List<int>> divisors = new List<List<int>>(); for (int i = 0; i <= n; i++) { divisors.Add(new List<int>()); } for (int i = 1; i <= n; i++) { for (int j = i; j <= n; j += i) { divisors[j].Add(i); } } return divisors; } // Function to calculate the product of // all proper divisors of each number in arr static void product_of_proper_divisors(int[] arr, int Q) { // Generate all divisors up to the maximum number in arr List<List<int>> divisors = sieve_of_eratosthenes(arr.Max()); // Calculate the product of all proper divisors for each number in arr for (int i = 0; i < Q; i++) { int n = arr[i]; int product = 1; // Multiply all divisors except for the number itself for (int j = 0; j < divisors[n].Count - 1; j++) { product *= divisors[n][j]; } Console.WriteLine(product); } } public static void Main(string[] args) { int[] arr = { 4, 6, 8, 16 }; int Q = arr.Length; Console.Write("Input: Q = " + Q + ", arr[] = {"); for (int i = 0; i < Q - 1; i++) { Console.Write(arr[i] + ", "); } Console.WriteLine(arr[Q - 1] + "}"); Console.WriteLine("Output:"); product_of_proper_divisors(arr, Q); int[] arr2 = { 3, 6, 9, 12 }; Q = arr2.Length; Console.Write("Input: Q = " + Q + ", arr[] = {"); for (int i = 0; i < Q - 1; i++) { Console.Write(arr2[i] + ", "); } Console.WriteLine(arr2[Q - 1] + "}"); Console.WriteLine("Output:"); product_of_proper_divisors(arr2, Q); }}// This code is contributed by Pushpesh Raj |
Javascript
//Javascript code for the above approach// Function to generate all divisors of numbers // up to n using a modified Sieve of Eratosthenesfunction sieveOfEratosthenes(n) { const divisors = new Array(n + 1).fill(null).map(() => []); for (let i = 1; i <= n; i++) { for (let j = i; j <= n; j += i) { divisors[j].push(i); } } return divisors;}// Function to calculate the product of // all proper divisors of each number in arrfunction productOfProperDivisors(arr) { // Generate all divisors up to the maximum number in arr const divisors = sieveOfEratosthenes(Math.max(...arr)); // Calculate the product of all proper divisors for each number in arr for (let i = 0; i < arr.length; i++) { const n = arr[i]; let product = 1; // Multiply all divisors except for the number itself for (let j = 0; j < divisors[n].length - 1; j++) { product *= divisors[n][j]; } console.log(product); }}const arr1 = [4, 6, 8, 16];console.log("Input: arr[] =", arr1);console.log("Output:");productOfProperDivisors(arr1);const arr2 = [3, 6, 9, 12];console.log("Input: arr[] =", arr2);console.log("Output:");productOfProperDivisors(arr2); |
Output
Input: Q = 4 arr[] = [4, 6, 8, 16] Output: 2 6 8 64 Input: Q = 4 arr[] = [3, 6, 9, 12] Output: 1 6 3 144
Time Complexity: O(Nlog(log(N)) + Qsqrt(N)), where Q is the number of queries and N is the maximum number in the array.
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!
