Dada una array arr[][] que consta de Q consultas donde cada fila consta de dos números L y R que denota el rango [L, R] ; la tarea es encontrar la suma del producto de los divisores propios de todos los números que se encuentran en el rango [L, R].
Nota: Dado que la respuesta puede ser muy grande, realice % con 1000000007 para cada consulta.
Ejemplos:
Entrada: Q = 2, arr[] = { { 4, 6 }, { 8, 10 } }
Salida: 9 21
Explicación:
Consulta 1: De 4 a 6
Producto de divisores propios de 4 = 1 * 2 = 2
Producto de divisores propios de 5 = 1
Producto de divisores propios de 6 = 1 * 2 * 3 = 6
Suma de producto de divisores propios de 4 a 6 = 2 + 1 + 6 = 9
Consulta 2: De 8 a 10
Producto de divisores propios de 8 = 1 * 2 * 4 = 8
Producto de divisores propios de 9 = 1 * 3 = 3
Producto de divisores propios de 10 = 1 * 2 * 5 = 10
Suma del producto de divisores propios de 8 a 10 = 8 + 3 + 10 = 21Entrada: Q = 2, arr[] = { { 10, 20 }, { 12, 16 } }
Salida: 975 238
Enfoque: dado que puede haber varias consultas y no es factible encontrar los divisores y el producto para cada consulta, la idea es precalcular y almacenar cada elemento junto con su producto de divisores adecuados en una array usando una modificación de Tamiz de Eratóstenes .
Una vez que el producto de los divisores propios de todos los números se almacena en una array, la idea es utilizar el concepto de array de suma de prefijos . La suma del producto de los divisores adecuados hasta ese índice en particular se calcula previamente y se almacena en una array pref[] para que cada consulta se pueda responder en un tiempo constante.
Para cada consulta, la suma de todos los productos de los divisores propios para el rango [L, R] se puede encontrar de la siguiente manera:
sum = pref[R] - pref[L - 1]
A continuación se muestra la implementación del enfoque anterior:
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
975 238