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

Dado un entero positivo N , la tarea es encontrar la suma de los divisores de todos los números del 1 al N .
Ejemplos: 

Entrada: N = 5 
Salida: 21 
Explicación: 
Suma de divisores de todos los números del 1 al 5 = 21. 
Divisores de 1 -> 1 
Divisores de 2 -> 1, 2 
Divisores de 3 -> 1, 3 
Divisores de 4 -> 1, 2, 4 
Divisores de 5 -> 1, 5, por lo tanto Suma = 21

Entrada: N = 6 
Salida: 33 
Explicación: 
Suma de divisores de todos los números del 1 al 6 = 33. 
Divisores de 1 -> 1 
Divisores de 2 -> 1, 2 
Divisores de 3 -> 1, 3 
Divisores de 4 -> 1, 2, 4 
Divisores de 5 -> 1, 5 
Divisores de 6 -> 1, 2, 3, 6, por lo tanto suma = 33 

Enfoque ingenuo y lineal: consulte la suma de todos los divisores de 1 a n para los enfoques ingenuo y lineal.
Enfoque logarítmico: consulte la suma de todos los divisores de 1 a N | Establecer 2 para el enfoque de tiempo logarítmico.

Enfoque eficiente: 
siga los pasos a continuación para resolver el problema:  

  • Podemos observar que para cada número x de 1 a N , ocurre en la suma hasta su mayor múltiplo que es ≤ N .
  • Por lo tanto, calcule la contribución de cada x mediante la fórmula x * piso (N / x) ,
  • Se puede observar que piso(N/i) es igual para una serie de números continuos l 1 , l 2 , l 3 ….l r . Por lo tanto, en lugar de calcular l i * floor(N/i) para cada i , calcule (l 1 + l 2 + l 3 +….+ l r ) * floor(N/l 1 ) , reduciendo así la complejidad computacional.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ Program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
 
#define int long long int
#define m 1000000007
 
// Function to find the sum
// of all divisors of all
// numbers from 1 to N
void solve(long long n)
{
 
    // Stores the sum
    long long s = 0;
 
    for (int l = 1; l <= n;) {
 
        // Marks the last point of
        // occurrence with same count
        int r = n / floor(n / l);
 
        int x = (((r % m) * ((r + 1)
                             % m))
                 / 2)
                % m;
        int y = (((l % m) * ((l - 1)
                             % m))
                 / 2)
                % m;
        int p = ((n / l) % m);
 
        // Calculate the sum
        s = (s + (((x - y) % m) * p) % m
             + m)
            % m;
 
        s %= m;
        l = r + 1;
    }
 
    // Return the result
    cout << (s + m) % m;
}
 
// Driver Code
signed main()
{
    long long n = 12;
    solve(n);
    return 0;
}

Java

// Java Program to implement
// the above approach
import java.util.*;
class GFG{
 
static final int m = 1000000007;
 
// Function to find the sum
// of all divisors of all
// numbers from 1 to N
static void solve(long n)
{
  // Stores the sum
  long s = 0;
 
  for (int l = 1; l <= n;)
  {
    // Marks the last point of
    // occurrence with same count
    int r = (int)(n /
             Math.floor(n / l));
 
    int x = (((r % m) *
             ((r + 1) %
               m)) / 2) % m;
    int y = (((l % m) *
             ((l - 1) %
               m)) / 2) % m;
    int p = (int)((n / l) % m);
 
    // Calculate the sum
    s = (s + (((x - y) %
                m) * p) %
                m + m) % m;
 
    s %= m;
    l = r + 1;
  }
 
  // Return the result
  System.out.print((s + m) % m);
}
 
// Driver Code
public static void main(String[] args)
{
  long n = 12;
  solve(n);
}
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 Program to implement
# the above approach
import math
m = 1000000007
 
# Function to find the sum
# of all divisors of all
# numbers from 1 to N
def solve(n):
   
    # Stores the sum
    s = 0;
    l = 1;
    while(l < n + 1):
       
        # Marks the last point of
        # occurrence with same count
        r = (int)(n /
             math.floor(n / l));
 
        x = ((((r % m) *
              ((r + 1) % m)) / 2) % m);
        y = ((((l % m) *
              ((l - 1) % m)) / 2) % m);
        p = (int)((n / l) % m);
 
        # Calculate the sum
        s = ((s + (((x - y) % m) *
                     p) % m + m) % m);
 
        s %= m;
        l = r + 1;
 
    # Return the result
    print (int((s + m) % m));
 
# Driver Code
if __name__ == '__main__':
   
    n = 12;
    solve(n);
 
# This code is contributed by Rajput-Ji

C#

// C# program to implement
// the above approach
using System;
 
class GFG{
 
static readonly int m = 1000000007;
 
// Function to find the sum
// of all divisors of all
// numbers from 1 to N
static void solve(long n)
{
   
  // Stores the sum
  long s = 0;
 
  for(int l = 1; l <= n;)
  {
     
    // Marks the last point of
    // occurrence with same count
    int r = (int)(n /(Math.Floor((double)n/l)));
 
    int x = (((r % m) *
             ((r + 1) %
             m)) / 2) % m;
    int y = (((l % m) *
             ((l - 1) %
             m)) / 2) % m;
    int p = (int)((n / l) % m);
 
    // Calculate the sum
    s = (s + (((x - y) %
               m) * p) %
                m + m) % m;
 
    s %= m;
    l = r + 1;
  }
   
  // Return the result
  Console.Write((s + m) % m);
}
 
// Driver Code
public static void Main(String[] args)
{
  long n = 12;
   
  solve(n);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript program implementation
// of the approach
 
let m = 1000000007;
  
// Function to find the sum
// of all divisors of all
// numbers from 1 to N
function solve(n)
{
  // Stores the sum
  let s = 0;
  
  for (let l = 1; l <= n;)
  {
    // Marks the last point of
    // occurrence with same count
    let r = (n /
             Math.floor(n / l));
  
    let x = Math.floor(((r % m) *
             ((r + 1) %
               m)) / 2) % m;
    let y = Math.floor(((l % m) *
             ((l - 1) %
               m)) / 2) % m;
    let p = (Math.floor(n / l) % m);
  
    // Calculate the sum
    s = (s + (((x - y) %
                m) * p) %
                m + m) % m;
  
    s %= m;
    l = r + 1;
  }
  
  // Return the result
  document.write((s + m) % m);
}
  
// Driver Code
     
    let n = 12;
  solve(n);
  
 // This code is contributed by splevel62.
</script>
Producción

127

Complejidad de Tiempo: O(√N) 
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

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