Given an array
arr[][]
consisting of
Q
queries where every row consists of two numbers
L
and
R
which denotes the range
[L, R]
; the task is to find the sum of the product of proper divisors of all numbers lying in the range [L, R].
Note:
Since the answer might be very big, perform
for every query.
Examples:
Input: Q = 2, arr[] = { { 4, 6 }, { 8, 10 } } Output: 9 21 Explanation: Query 1: From 4 to 6 Product of proper divisors of 4 = 1 * 2 = 2 Product of proper divisors of 5 = 1 Product of proper divisors of 6 = 1 * 2 * 3 = 6 Sum of product of proper divisors from 4 to 6 = 2 + 1 + 6 = 9 Query 2: From 8 to 10 Product of proper divisors of 8 = 1 * 2 * 4 = 8 Product of proper divisors of 9 = 1 * 3 = 3 Product of proper divisors of 10 = 1 * 2 * 5 = 10 Sum of product of proper divisors from 8 to 10 = 8 + 3 + 10 = 21 Input: Q = 2, arr[] = { { 10, 20 }, { 12, 16 } } Output: 975 238
Approach:
Since there can be multiple queries and finding the divisors and product for every query is not feasible, the idea is to precompute and store every element along with its product of proper divisors in an array using a modification of
. Once the product of the proper divisors of all the numbers is stored in an array, the idea is to use the concept of
. The sum of the product of proper divisors till that particular index is precomputed and stored in an array
pref[]
so that every query can be answered in constant time. For each query, the sum of all product of proper divisors for the range
[L, R]
can be found as follows:
sum = pref[R] - pref[L - 1]
Below is the implementation of the above approach:
CPP
// C++ implementation to find the sum // of the product of proper divisors of // all the numbers lying in the range [L, R] #include <bits/stdc++.h> #define ll long long int #define mod 1000000007 using namespace std; // Vector to store the product // of the proper divisors of a number vector<ll> ans(100002, 1); // Variable to store the prefix // sum of the product array long long pref[100002]; // Function to precompute the product // of proper divisors of a number at // it's corresponding index void preCompute() { // Modificatino of sieve to store the // product of the proper divisors for ( int i = 2; i <= 100000 / 2; i++) { for ( int j = 2 * i; j <= 100000; j += i) { // Multiplying the existing value // with i because i is the // proper divisor of ans[j] ans[j] = (ans[j] * i) % mod; } } // Loop to store the prefix sum of the // previously computed product array for ( int i = 1; i < 100002; ++i) { // Computing the prefix sum pref[i] = pref[i - 1] + ans[i]; pref[i] %= mod; } } // Function to print the sum // for each query void printSum( int L, int R) { cout << pref[R] - pref[L - 1] << " " ; } // Function to print te sum of product // of proper divisors of a number in // [L, R] void printSumProper( int arr[][2], int Q) { // Calling the function that // pre computes // the sum of product // of proper divisors preCompute(); // Iterate over all Queries // to print the sum for ( int i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } // Driver code int main() { int Q = 2; int arr[][2] = { { 10, 20 }, { 12, 16 } }; printSumProper(arr, Q); return 0; } |
Java
// Java implementation to find the sum // of the product of proper divisors of // all the numbers lying in the range [L, R] import java.util.*; class GFG{ static int mod = 1000000007 ; // Vector to store the product // of the proper divisors of a number static int []ans = new int [ 100002 ]; // Variable to store the prefix // sum of the product array static int []pref = new int [ 100002 ]; // Function to precompute the product // of proper divisors of a number at // it's corresponding index static void preCompute() { // Modificatino of sieve to store the // product of the proper divisors Arrays.fill(ans, 1 ); for ( int i = 2 ; i <= 100000 / 2 ; i++) { for ( int j = 2 * i; j <= 100000 ; j += i) { // Multiplying the existing value // with i because i is the // proper divisor of ans[j] ans[j] = (ans[j] * i) % mod; } } // Loop to store the prefix sum of the // previously computed product array for ( int i = 1 ; i < 100002 ; ++i) { // Computing the prefix sum pref[i] = pref[i - 1 ] + ans[i]; pref[i] %= mod; } } // Function to print the sum // for each query static void printSum( int L, int R) { System.out.print(pref[R] - pref[L - 1 ]+ " " ); } // Function to print te sum of product // of proper divisors of a number in // [L, R] static void printSumProper( int [][]arr, int Q) { // Calling the function that // pre computes // the sum of product // of proper divisors preCompute(); // Iterate over all Queries // to print the sum for ( int i = 0 ; i < Q; i++) { printSum(arr[i][ 0 ], arr[i][ 1 ]); } } // Driver code public static void main(String args[]) { int Q = 2 ; int [][] arr = {{ 10 , 20 }, { 12 , 16 } }; printSumProper(arr, Q); } } // This code is contributed by Surendra_Gangwar |
Python3
# Python3 implementation to find the sum # of the product of proper divisors of # all the numbers lying in the range [L, R] mod = 1000000007 # Vector to store the product # of the proper divisors of a number ans = [ 1 ] * ( 100002 ) # Variable to store the prefix # sum of the product array pref = [ 0 ] * 100002 # Function to precompute the product # of proper divisors of a number at # it's corresponding index def preCompute(): # Modificatino of sieve to store the # product of the proper divisors for i in range ( 2 , 100000 / / 2 + 1 ): for j in range ( 2 * i, 100000 + 1 ,i): # Multiplying the existing value # with i because i is the # proper divisor of ans[j] ans[j] = (ans[j] * i) % mod # Loop to store the prefix sum of the # previously computed product array for i in range ( 1 , 100002 ): # Computing the prefix sum pref[i] = pref[i - 1 ] + ans[i] pref[i] % = mod # Function to prthe sum # for each query def printSum(L, R): print (pref[R] - pref[L - 1 ],end = " " ) # Function to prte sum of product # of proper divisors of a number in # [L, R] def printSumProper(arr, Q): # Calling the function that # pre computes # the sum of product # of proper divisors preCompute() # Iterate over all Queries # to prthe sum for i in range (Q): printSum(arr[i][ 0 ], arr[i][ 1 ]) # Driver code if __name__ = = '__main__' : Q = 2 arr = [ [ 10 , 20 ], [ 12 , 16 ] ] printSumProper(arr, Q) # This code is contributed by mohit kumar 29 |
C#
using System; class GFG { static int mod = 1000000007; // Array to store the product // of the proper divisors of a number static int [] ans = new int [100002]; // Array to store the prefix // sum of the product array static int [] pref = new int [100002]; // Function to precompute the product // of proper divisors of a number at // its corresponding index static void PreCompute() { // Modification of sieve to store the // product of the proper divisors Array.Fill(ans, 1); for ( int i = 2; i <= 100000 / 2; i++) { for ( int j = 2 * i; j <= 100000; j += i) { // Multiplying the existing value // with i because i is the // proper divisor of ans[j] ans[j] = ( int )(( long )ans[j] * i % mod); } } // Loop to store the prefix sum of the // previously computed product array for ( int i = 1; i < 100002; ++i) { // Computing the prefix sum pref[i] = (pref[i - 1] + ans[i]) % mod; } } // Function to print the sum // for each query static void PrintSum( int L, int R) { Console.Write((pref[R] - pref[L - 1]) + " " ); } // Function to print the sum of product // of proper divisors of a number in // [L, R] static void PrintSumProper( int [][] arr, int Q) { // Calling the function that // precomputes the sum of product // of proper divisors PreCompute(); // Iterate over all Queries // to print the sum for ( int i = 0; i < Q; i++) { PrintSum(arr[i][0], arr[i][1]); } } // Driver code public static void Main( string [] args) { int Q = 2; int [][] arr = { new int [] { 10, 20 }, new int [] { 12, 16 } }; PrintSumProper(arr, Q); } } // code is contributed by shinjanpatra |
Javascript
const mod = 1000000007; // Array to store the product of proper divisors of a number const ans = new Array(100002).fill(1); // Array to store the prefix sum of the product array const pref = new Array(100002).fill(0); // Function to precompute the product of proper divisors of a number at its corresponding index function preCompute() { // Modification of the sieve to store the product of proper divisors for (let i = 2; i <= 100000 / 2; i++) { for (let j = 2 * i; j <= 100000; j += i) { // Multiplying the existing value with 'i' because 'i' is the proper divisor of 'ans[j]' ans[j] = (ans[j] * i) % mod; } } // Loop to store the prefix sum of the previously computed product array for (let i = 1; i < 100002; i++) { // Computing the prefix sum pref[i] = (pref[i - 1] + ans[i]) % mod; } } // Function to print the sum for each query function printSum(L, R) { console.log(pref[R] - pref[L - 1]); } // Function to print the sum of the product of proper divisors of a number in [L, R] function printSumProper(arr, Q) { // Calling the function that precomputes the sum of the product of proper divisors preCompute(); // Iterate over all queries to print the sum for (let i = 0; i < Q; i++) { printSum(arr[i][0], arr[i][1]); } } // Driver code const Q = 2; const arr = [ [10, 20], [12, 16] ]; printSumProper(arr, Q); |
975 238
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!