Bueno, intentaré la siguiente solución rápida y sucia que puede mejorarse. Además, espero que este problema no sea parte de algún concurso una vez más.
Estamos tratando de calcular [math] \ mathrm {CSOD} (n) [/ math].
Los divisores de números [matemáticos] \ leq n [/ matemáticos] adecuados ([matemática] \ neq 1 [/ matemática]) están en el rango [matemática] 2, \ ldots \ lfloor \ frac {n} {2} \ rfloor [ /matemáticas].
¿Cuántos [matemática] 2 [/ matemática] hay entre divisores? Aproximadamente la mitad de los números.
- Cómo demostrar que el único par de enteros positivos que satisface a + b = ab es (2,2)
- Se le dan enteros N y D. ¿Qué es un programa para encontrar N enteros positivos x1, xN de manera que la diferencia de su producto y su suma sea igual a la entrada D?
- Relaciones de recurrencia: ¿Cuál es la suma máxima que se puede formar?
- ¿Cuántos enteros [matemáticas] x \ en \ {1, 2, 3, \ ldots, 99, 100 \} [/ matemáticas] hay tales que [matemáticas] x ^ 2 + x ^ 3 [/ matemáticas] es el cuadrado de un entero?
- Cómo encontrar el módulo de grandes combinaciones como nCr mod p donde p es un número primo
Para ser más precisos, su suma es [math] 2 \ lfloor \ frac {n} {2} \ rfloor -2. [/ Math] (Restamos 2 ya que 2 no es un divisor propio del número 2)
Por la lógica similar, la suma de todos los divisores [matemática] s [/ matemática] en estos números
es [math] s \ lfloor \ frac {n} {s} \ rfloor -s. [/ math]
Ahora observe que [math] n – s \ lfloor \ frac {n} {s} \ rfloor = r_s, [/ math] donde [math] r_s [/ math] es el resto de la división de [math] n [/ math ] por [matemáticas] s. [/ matemáticas]
Deje [math] m = \ lfloor \ frac {n} {2} \ rfloor [/ math].
Luego, al sumar todos los divisores se obtiene [math] \ displaystyle n (m-1) – \ sum_ {k = 2} ^ {m} k – \ sum_ {k = 2} ^ {m} r_k = [/ math] [math] n \ cdot (m-1) – \ frac {(m + 2) (m-1)} {2} – \ sum_ {k = 2} ^ {m} r_k. [/ math]
La parte más fea es el cálculo de [matemáticas] \ sum_ {k = 2} ^ {m} r_k [/ matemáticas]; el cálculo directo de esto requiere operaciones aritméticas [math] \ mathcal {O} (n) [/ math].
Ejemplo: [matemáticas] n = 10 [/ matemáticas]. Entonces [matemáticas] m = 5 [/ matemáticas].
Por algún abuso de notación denotar división descansa por [math] \ mathrm {mod} [/ math]
[matemáticas] \ mathrm {CSOD} (10) = 10 \ cdot 4 – \ frac {7 \ cdot 4} {2} – 10 \ mod 2 -10 \ mod 3 – 10 \ mod 4 – 10 \ mod 5 = 40 -14-3 = 23. [/ Matemáticas]
Así que redujimos el problema a un cálculo eficiente de [math] \ sum_ {k = 2} ^ {m} r_k [/ math].
Creo que el algoritmo directo puede mejorarse ligeramente.
Por ejemplo, si sé que [matemática] n \ mod 100 = r [/ matemática] entonces usando esta [matemática] r [/ matemática] puedo reemplazar [matemática] n \ mod d [/ matemática] por [matemática] r \ mod d [/ math] para cada [math] d [/ math] que es un divisor de [math] 100 [/ math].