3 votos

Cómo encontrar la suma de $k$ potencias de todos los divisores propios de la primera $n$ números

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

Spoj 14175. Factor de potencia Suma (dura)

2voto

irrational John Puntos 2478

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$$ .

Result Suma1 Suma2 Suma3 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).

1voto

Shabaz Puntos 403

Tenga en cuenta que $2$ es un factor propio de la mitad de los números menos $1$ por lo que si el límite superior es $n$ contribuirá $(\lfloor \frac n2 \rfloor -1) 2^k$ a la suma. Esto evita la factorización de cualquiera de los números.

1voto

Concrete Donkey Puntos 155

Simplemente cuente el número de veces $m$ aparece en la lista de todos los divisores de $\{1,2,...,n\}$ Es decir, es $[\frac{n}{m}]$ (donde, $[a]$ es el suelo de $a$ ). Por lo tanto, la suma de $k$ -La potencia de los divisores propios es $\sum\limits_{m=2}^n m^k([\frac{n}{m}]-1)$ .

i-Ciencias.com

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.

Powered by:

X