Sum of product of proper divisors of all Numbers lying in range [ L , R ] | C ++ implementation to find the sum of the product of proper divisors of all the numbers lying in the range [ L , R ] ; Vector to store the product of the proper divisors of a number ; Variable to store the prefix sum of the product array ; Function to precompute the product of proper divisors of a number at it 's corresponding index ; Modificatino of sieve to store the product of the proper divisors ; Multiplying the existing value with i because i is the proper divisor of ans [ j ] ; Loop to store the prefix sum of the previously computed product array ; Computing the prefix sum ; Function to print the sum for each query ; Function to print te sum of product of proper divisors of a number in [ L , R ] ; Calling the function that pre computes the sum of product of proper divisors ; Iterate over all Queries to print the sum ; Driver code
#include <bits/stdc++.h> NEW_LINE #define ll  long long int NEW_LINE #define mod  1000000007 NEW_LINE using namespace std ; vector < ll > ans ( 100002 , 1 ) ; long long pref [ 100002 ] ; 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 ; } } for ( int i = 1 ; i < 100002 ; ++ i ) { pref [ i ] = pref [ i - 1 ] + ans [ i ] ; pref [ i ] %= mod ; } } void printSum ( int L , int R ) { cout << pref [ R ] - pref [ L - 1 ] << " ▁ " ; } void printSumProper ( int arr [ ] [ 2 ] , int Q ) { preCompute ( ) ; for ( int i = 0 ; i < Q ; i ++ ) { printSum ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; } } int main ( ) { int Q = 2 ; int arr [ ] [ 2 ] = { { 10 , 20 } , { 12 , 16 } } ; printSumProper ( arr , Q ) ; return 0 ; }