Suma de todos los divisores de 1 a N | conjunto 2

Posted on by Rudeus Greyrat

Dado un entero positivo N , la tarea es encontrar la suma de los divisores de los primeros N números naturales.

Ejemplos:

Entrada: N = 4 
Salida: 15 
Explicación: 
Suma de divisores de 1 = (1) 
Suma de divisores de 2 = (1+2) 
Suma de divisores de 3 = (1+3) 
Suma de divisores de 4 = (1+ 2+4) 
Por lo tanto, la suma total = 1 + (1+2) + (1+3) + (1+2+4) = 15 

Entrada: N = 5 
Salida: 21 
Explicación: 
Suma de divisores de 1 = (1) 
Suma de divisores de 2 = (1+2) 
Suma de divisores de 3 = (1+3) 
Suma de divisores de 4 = (1+ 2+4) 
Suma de divisores de 5 = (1+5) 
Por lo tanto, suma total = (1) + (1+2) + (1+3) + (1+2+4) + (1+5) = 21 

Para un enfoque de tiempo lineal, consulte Suma de todos los divisores de 1 a N

Enfoque: 
para optimizar el enfoque en la publicación mencionada anteriormente, debemos buscar una solución con complejidad logarítmica. Un número D se agrega varias veces en la respuesta final. Tratemos de observar un patrón de adición repetitiva. 
Considerando N = 12 :

D Número de veces añadido
1 12
2 6
3 4
5, 6 2
7, 8, 9, 10, 11, 12 1

Del patrón anterior, observe que cada número D se suma ( N / D ) veces. Además, hay múltiples D que tienen el mismo (N/D). Por lo tanto, podemos concluir que para un N dado , y un i particular , los números de ( N / ( i + 1 )) + 1 a ( N / i ) se sumarán i veces. 

Ilustración: 
 

  1. N = 12, i = 1 
    (N/(i+1))+1 = 6+1 = 7 y (N/i) = 12 
    Todos los números serán 7, 8, 9, 10, 11, 12 y serán añadido 1 vez solamente.
  2. N = 12, i = 2 
    (N/(i+1))+1 = 4+1 = 5 y (N/i) = 6 
    Todos los números serán 5, 6 y se sumarán 2 veces.

Ahora, suponga que A = (N / (i + 1)), B = (N / i) 
Suma de números de A + 1 a B = Suma de números de 1 a B – Suma de números de 1 a A 
También, en lugar de simplemente incrementar i cada vez en 1, encuentre el siguiente me gusta esto, i = N/(N/(i+1))

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;
 
int mod = 1000000007;
  
// Functions returns sum
// of numbers from 1 to n
int linearSum(int n)
{
    return (n * (n + 1) / 2) % mod;
}
  
// Functions returns sum
// of numbers from a+1 to b
int rangeSum(int b, int a)
{
    return (linearSum(b) -
            linearSum(a)) % mod;
}
 
// Function returns total
// sum of divisors
int totalSum(int n)
{
     
    // Stores total sum
    int result = 0;
    int i = 1;
  
    // Finding numbers and
    //its occurrence
    while(true)
    {
          
        // Sum of product of each
        // number and its occurrence
        result += rangeSum(n / i, n / (i + 1)) *
                          (i % mod) % mod;
          
        result %= mod;
         
        if (i == n)
            break;
             
        i = n / (n / (i + 1));
    }
    return result;
}       
  
// Driver code
int main()
{
    int N = 4;
    cout << totalSum(N) << endl;
  
    N = 12;
    cout << totalSum(N) << endl;
    return 0;
}
 
// This code is contributed by rutvik_56

Java

// Java program for
// the above approach
class GFG{
     
static final int mod = 1000000007;
 
// Functions returns sum
// of numbers from 1 to n
public static int linearSum(int n)
{
    return (n * (n + 1) / 2) % mod;
}
   
// Functions returns sum
// of numbers from a+1 to b
public static int rangeSum(int b, int a)
{
    return (linearSum(b) -
            linearSum(a)) % mod;
}
  
// Function returns total
// sum of divisors
public static int totalSum(int n)
{
      
    // Stores total sum
    int result = 0;
    int i = 1;
   
    // Finding numbers and
    //its occurrence
    while(true)
    {
           
        // Sum of product of each
        // number and its occurrence
        result += rangeSum(n / i,
                           n / (i + 1)) *
                          (i % mod) % mod;
           
        result %= mod;
          
        if (i == n)
            break;
              
        i = n / (n / (i + 1));
    }
    return result;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 4;
    System.out.println(totalSum(N));
   
    N = 12;
    System.out.println(totalSum(N));
}
}
 
// This code is contributed by divyeshrabadiya07

Python3

# Python3 program for
# the above approach
 
mod = 1000000007
 
# Functions returns sum
# of numbers from 1 to n
def linearSum(n):
    return n*(n + 1)//2 % mod
 
# Functions returns sum
# of numbers from a+1 to b
def rangeSum(b, a):
    return (linearSum(b) - (
          linearSum(a))) % mod
 
# Function returns total
# sum of divisors
def totalSum(n):
 
    # Stores total sum
    result = 0
    i = 1
 
    # Finding numbers and
    # its occurrence
    while True:
         
        # Sum of product of each
        # number and its occurrence
        result += rangeSum(
            n//i, n//(i + 1)) * (
                  i % mod) % mod;
         
        result %= mod;
        if i == n:
            break
        i = n//(n//(i + 1))
         
    return result       
 
# Driver code
 
N= 4
print(totalSum(N))
 
N= 12
print(totalSum(N))

C#

// C# program for
// the above approach
using System;
 
class GFG{
     
static readonly int mod = 1000000007;
 
// Functions returns sum
// of numbers from 1 to n
public static int linearSum(int n)
{
    return (n * (n + 1) / 2) % mod;
}
   
// Functions returns sum
// of numbers from a+1 to b
public static int rangeSum(int b, int a)
{
    return (linearSum(b) -
            linearSum(a)) % mod;
}
  
// Function returns total
// sum of divisors
public static int totalSum(int n)
{
     
    // Stores total sum
    int result = 0;
    int i = 1;
   
    // Finding numbers and
    //its occurrence
    while(true)
    {
           
        // Sum of product of each
        // number and its occurrence
        result += rangeSum(n / i,
                           n / (i + 1)) *
                          (i % mod) % mod;
           
        result %= mod;
          
        if (i == n)
            break;
              
        i = n / (n / (i + 1));
    }
    return result;
}
 
// Driver code
public static void Main(String[] args)
{
    int N = 4;
    Console.WriteLine(totalSum(N));
   
    N = 12;
    Console.WriteLine(totalSum(N));
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// JavaScript program for
// the above approach
let mod = 1000000007;
 
// Functions returns sum
// of numbers from 1 to n
function linearSum(n)
{
    return (n * (n + 1) / 2) % mod;
}
   
// Functions returns sum
// of numbers from a+1 to b
function rangeSum(b, a)
{
    return (linearSum(b) -
            linearSum(a)) % mod;
}
  
// Function returns total
// sum of divisors
function totalSum(n)
{
      
    // Stores total sum
    let result = 0;
    let i = 1;
   
    // Finding numbers and
    //its occurrence
    while(true)
    {
           
        // Sum of product of each
        // number and its occurrence
        result += rangeSum(Math.floor(n / i),
                           Math.floor(n / (i + 1))) *
                                     (i % mod) % mod;
           
        result %= mod;
          
        if (i == n)
            break;
              
        i = Math.floor(n / (n / (i + 1)));
    }
    return result;
}
   
// Driver Code
let N = 4;
document.write(totalSum(N) + "<br/>");
 
N = 12;
document.write(totalSum(N));
   
// This code is contributed by susmitakundugoaldanga
 
</script>
Producción: 

15
127

 

Complejidad del tiempo: O(√n)

Publicación traducida automáticamente

Artículo escrito por rohitpal210 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 *