Dado un entero positivo N , la tarea es encontrar la suma del producto de todos los enteros en el rango [1, N] con su cuenta de divisores .
Ejemplos:
Entrada: N = 3
Salida: 11
Explicación:
El número de divisores positivos de 1 es 1 (es decir, 1 mismo). Por lo tanto, f(1) = 1.
El número de divisores positivos de 2 es 2 (es decir, 1, 2). Por lo tanto, f(2) = 2.
El número de divisores positivos de 3 es 2 (es decir, 1, 3). Por lo tanto, f(3) = 2.
Entonces la respuesta es 1*f(1) + 2*f(2) + 3*f(3) = 1*1 + 2*2 + 3*2 = 11.Entrada: N = 4
Salida: 23
Explicación:
Aquí f(1) = 1, f(2) = 2, f(3) = 2 y f(4) = 3. Entonces, la respuesta es 1*1 + 2* 2 + 3*2 + 4*3 = 23.
Enfoque ingenuo: El enfoque ingenuo es atravesar de 1 a N y encontrar la suma de todos los números con su cuenta de divisores .
Complejidad de tiempo: O(N*sqrt(N))
Espacio auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es considerar la contribución total que cada número hace a la respuesta. A continuación se muestran los pasos:
- Para cualquier número X en el rango [1, N] , X aporta K a la suma de cada K de 1 a N tal que K es un múltiplo de X .
- Obsérvese que la lista de estos K es de forma i, 2i, 3i, …, Fi donde F es el número de múltiplos de i entre 1 y N .
- Por lo tanto, para encontrar la suma de estos números generados arriba está dado por
i*(1+2+3 + … F) = i*(F*(F+1))/2.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
long long sumOfFactors(int N)
{
long long ans = 0;
// Iterate for every number
// between 1 and N
for (int i = 1; i <= N; i++) {
// Find the first multiple
// of i between 1 and N
long long first = i;
// Find the last multiple
// of i between 1 and N
long long last = (N / i) * i;
// Find the total count of
// multiple of in [1, N]
long long factors
= (last - first) / i + 1;
// Compute the contribution of i
// using the formula
long long totalContribution
= (((factors) * (factors + 1)) / 2) * i;
// Add the contribution
// of i to the answer
ans += totalContribution;
}
// Return the result
return ans;
}
// Driver code
int main()
{
// Given N
int N = 3;
// function call
cout << sumOfFactors(N);
}
Java
// Java program for the above approach
class GFG{
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
static int sumOfFactors(int N)
{
int ans = 0;
// Iterate for every number
// between 1 and N
for (int i = 1; i <= N; i++)
{
// Find the first multiple
// of i between 1 and N
int first = i;
// Find the last multiple
// of i between 1 and N
int last = (N / i) * i;
// Find the total count of
// multiple of in [1, N]
int factors = (last - first) / i + 1;
// Compute the contribution of i
// using the formula
int totalContribution = (((factors) *
(factors + 1)) / 2) * i;
// Add the contribution
// of i to the answer
ans += totalContribution;
}
// Return the result
return ans;
}
// Driver code
public static void main(String[] args)
{
// Given N
int N = 3;
// function call
System.out.println(sumOfFactors(N));
}
}
// This code is contributed by Ritik Bansal
Python3
# Python3 implementation of # the above approach # Function to find the sum of the # product of all the integers and # their positive divisors up to N def sumOfFactors(N): ans = 0 # Iterate for every number # between 1 and N for i in range(1, N + 1): # Find the first multiple # of i between 1 and N first = i # Find the last multiple # of i between 1 and N last = (N // i) * i # Find the total count of # multiple of in [1, N] factors = (last - first) // i + 1 # Compute the contribution of i # using the formula totalContribution = (((factors * (factors + 1)) // 2) * i) # Add the contribution # of i to the answer ans += totalContribution # Return the result return ans # Driver Code # Given N N = 3 # Function call print(sumOfFactors(N)) # This code is contributed by Shivam Singh
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
static int sumOfFactors(int N)
{
int ans = 0;
// Iterate for every number
// between 1 and N
for (int i = 1; i <= N; i++)
{
// Find the first multiple
// of i between 1 and N
int first = i;
// Find the last multiple
// of i between 1 and N
int last = (N / i) * i;
// Find the total count of
// multiple of in [1, N]
int factors = (last - first) / i + 1;
// Compute the contribution of i
// using the formula
int totalContribution = (((factors) *
(factors + 1)) / 2) * i;
// Add the contribution
// of i to the answer
ans += totalContribution;
}
// Return the result
return ans;
}
// Driver code
public static void Main(String[] args)
{
// Given N
int N = 3;
// function call
Console.WriteLine(sumOfFactors(N));
}
}
// This code is contributed by gauravrajput1
Javascript
<script>
// javascript program for the above approach
// Function to find the sum of the
// product of all the integers and
// their positive divisors up to N
function sumOfFactors(N)
{
var ans = 0;
// Iterate for every number
// between 1 and N
for (i = 1; i <= N; i++)
{
// Find the first multiple
// of i between 1 and N
var first = i;
// Find the last multiple
// of i between 1 and N
var last = parseInt(N / i) * i;
// Find the total count of
// multiple of in [1, N]
var factors = parseInt((last - first) / i )+ 1;
// Compute the contribution of i
// using the formula
var totalContribution = parseInt(((factors) * (factors + 1)) / 2) * i;
// Add the contribution
// of i to the answer
ans += totalContribution;
}
// Return the result
return ans;
}
// Driver code
// Given N
var N = 3;
// function call
document.write(sumOfFactors(N));
// This code is contributed by todaysgaurav.
</script>
11
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por aqibmahboob1999 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA