Suma del producto de los divisores propios de todos los números que se encuentran en el rango [L, R]

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 = 21

Entrada: 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
Producción:

975 238

Publicación traducida automáticamente

Artículo escrito por spp____ y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *