¿Por qué mi solución C ++ al problema SPOJ.com – Problema DIVSUM2 muestra un error?

Su programa excede el límite de tiempo.
Puede intentar optimizar su solución O (n) a O (sqrt (n)) mediante una simple observación de la siguiente manera.

Considere que el número dado es 24. Su código itera 24 veces para encontrar los factores 1,2,3,4,6,8,12 y 24.
Como puedes observar 24 = 8 × 3 = 3 × 8.
Entonces, en lugar de iterar 24 veces, puede ir hasta ceil (sqrt (24)) ~ 5 y resumir para (supongamos que la variable iteradora es i) i + (n / i). Además, trate de verificar si hay casos de esquina y AC.

24 es un número bastante pequeño. Solo imagine el tiempo de ejecución para un gran número como 1,000,000 en el que su solución iteraría 1000,000 veces y utilizando el método anterior puede obtener la respuesta en solo 1000 iteraciones.

PD: implementé el método anterior y obtuve un AC.

La razón por la que obtiene un TLE es porque iterar a través de cada número antes de que el número dado no sea simplemente lo suficientemente rápido.

El mejor enfoque es expresar el número en términos de factores primos, luego encontrar cada factor y luego evaluar la suma.

Por ejemplo, el número 24 se puede representar como 2 ^ 3 * 3.

Luego encuentre todos los factores, a saber, 2,3, 2 * 3, 2 * 2, 2 * 2 * 3, 2 * 2 * 2 y agréguelos.

Espero eso ayude

Me enfrenté a un problema similar cuando intentaba resolver un problema de codechef similar. El operador de extracción que utiliza c ++ consume bastante tiempo. Use scanf en su lugar. Puede pensar que no es C ++ pero está bien … pruébelo