Estoy intentando este problema pero no consigo dar con un algoritmo eficiente ¿puede alguien ayudarme con este problema? He resuelto la versión más fácil del problema Abajo está el enlace del problema.
Gracias de antemano
Estoy intentando este problema pero no consigo dar con un algoritmo eficiente ¿puede alguien ayudarme con este problema? He resuelto la versión más fácil del problema Abajo está el enlace del problema.
Gracias de antemano
Suma de tp r9m respuesta: El problema original te pide la suma de todos los divisores, contando $n$ como divisor de $n$ . Una cosa interesante a tener en cuenta aquí es que $$\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor i^k=\sum_{i=1}^x \sum_{j=1}^{\lfloor n/i\rfloor} j^k-x\sum_{j=1}^{\lfloor n/x\rfloor}j^k+\sum_{i=1}^{\lfloor n/x \rfloor} \left\lfloor\frac{n}{i}\right\rfloor i^k\tag1$$ .
Esto se puede generalizar y demostrar gráficamente como sigue: Para cualquier $f$ y $x,n\in \mathbb N$ tal que $0<x\le n$ $$\color{#96A}{\sum_{i=1}^n\left\lfloor\frac{n}{i}\right\rfloor f(i)}=\color{#5A5}{\sum_{i=1}^x \sum_{j=1}^{\lfloor n/i\rfloor}f(j)}-\color{#B55}{x\sum_{i=1}^{\lfloor n/x\rfloor}f(i)}+\color{#68A}{\sum_{i=1}^{\lfloor n/x\rfloor} \left\lfloor\frac{n}{i}\right\rfloor f(i)} \tag2$$ .
Nota: En realidad no hay ningún problema si $x$ no está en uno de los pasos de la escalera La prueba sigue funcionando.
Pero, ¿por qué íbamos a hacer algo así? Bueno, si se establece $x=\lfloor \sqrt n\rfloor$ ya que podemos calcular $$\sum_{i=1}^{x}i^k$$ en constante (asumiendo la aritmética básica del tiempo contante) tiempo utilizando Polinomios de Faulhaber hemos reducido efectivamente el número de operaciones necesarias para calcular $(1)$ a $O(\sqrt n)$ . Por desgracia, necesitamos tener un conocimiento previo del límite del límite de $k$ para que podamos codificar los polinomios necesarios (pero por suerte, el límite dado en el problema es $1\le k\le10$ que son exactamente los polinomios que puedes encontrar en el enlace).
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.