Skip to Content
CTRL K

Sum of Divisors

Pista 1

n=1012n=10^{12} implica que la complejidad temporal deseada es O(n)\mathcal{O}(\sqrt n).

Pista 2

Calcular la suma de los divisores de cada número de 11 a nn parece imposible: incluso si se pudiera en tiempo constante la solución igual daría TLE.

¿Y si en lugar de partir de los números, partimos de los divisores?

Solución

Explicación

Como se menciona en la Pista 2, partamos de los divisores en lugar de los números.

Si consideramos cualquier divisor dd, observemos que siempre aparece ⌊nd⌋\left\lfloor \frac{n}{d}\right\rfloor veces si listamos todos los divisores de los números de 11 a nn.

Así, para obtener la respuesta solo hay que calcular la siguiente expresión:

∑d=1nd⌊nd⌋ \sum_{d=1}^{n} d\left\lfloor \frac{n}{d}\right\rfloor

Pero calcular esto por fuerza bruta da una solución O(n)\mathcal{O}(n), que sigue siendo demasiado lenta.

Sin embargo, si listamos los valores de ⌊nd⌋\left\lfloor \frac{n}{d}\right\rfloor (de ahora en adelante qq) para valores de nn suficientemente grandes, observemos que los valores empiezan a formar “cadenas” largas del mismo valor. Por ejemplo, esta es la lista de valores para n=20n=20:

[20,10,6,5,4,3,2,2,2,2,1,1,1,1,1,1,1,1,1,1] [20, 10, 6, 5, 4, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Llevando este patrón más lejos, se puede mostrar que hay a lo sumo 2n2\sqrt{n} valores distintos de qq (demostración aquí ).

Sabiendo esto, podemos procesar rápido todos los términos de la sumatoria con el mismo valor de qq. Empezamos con d=1d=1 y saltamos al siguiente valor que produce un qq distinto en lugar de incrementarlo de forma naive en 11.

Solución en video

Nota: La solución en video puede no ser la misma que las otras soluciones. Código en C++.

Video de YouTube (JqWiWJQOQyU )

Implementación

Complejidad temporal: O(n)\mathcal{O}(\sqrt n)

#include <iostream>
 
using std::cout;
using std::endl;
 
const int MOD = 1e9 + 7;
const int TWO_MOD_INV = 500000004;
 
/** @return La suma de todos los números en [start, end] módulo MOD. */
long long total_sum(long long start, long long end) {
	return ((((end - start + 1) % MOD) * ((start + end) % MOD) % MOD) * TWO_MOD_INV %
	        MOD);
}
 
int main() {
	long long n;
	std::cin >> n;
 
	long long total = 0;
	long long at = 1;
	while (at <= n) {
		long long add_amt = n / at;  // Nuestro divisor a procesar
		// El número más grande que todavía tiene el mismo valor de q
		long long last_same = n / add_amt;
 
		total = (total + add_amt * total_sum(at, last_same)) % MOD;
		at = last_same + 1;
	}
 
	cout << total << endl;
}
import java.io.*;
 
public class DivisorSum {
	static final int MOD = (int)1e9 + 7;
	static final int TWO_MOD_INV = 500000004;
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(read.readLine());
 
		long total = 0;
		long at = 1;
		while (at <= n) {
			long add_amt = n / at;  // Nuestro divisor a procesar
			// El número más grande que todavía tiene el mismo valor de q
			long last_same = n / add_amt;
 
			total = (total + add_amt * totalSum(at, last_same)) % MOD;
			at = last_same + 1;
		}
 
		System.out.println(total);
	}
 
	/** @return La suma de todos los números en [start, end] módulo MOD. */
	static long totalSum(long start, long end) {
		return ((((end - start + 1) % MOD) * ((start + end) % MOD) % MOD) *
		        TWO_MOD_INV % MOD);
	}
}
MOD = 10**9 + 7
 
 
def total_sum(start: int, end: int) -> int:
	"""Devuelve la suma de todos los números en [start, end]."""
	return (end - start + 1) * (start + end) // 2
 
 
n = int(input())
 
total = 0
at = 1
while at <= n:
	add_amt = n // at  # Nuestro divisor a procesar
	# El número más grande que todavía tiene el mismo valor de q
	last_same = n // add_amt
 
	total += add_amt * total_sum(at, last_same)
	at = last_same + 1
 
print(total % MOD)

Loan Repayment  usa una idea similar.

Fundamentos