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