Editorial for Suma simple


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Primera Subtarea:

Podemos recorrer el rango de 1 a n y usar la primera fórmula de la editorial.

Segunda Subtarea:

Para esta subtarea debemos calcular \phi_{n} de una manera medianamente eficiente, existen dos formas, una con inclusión-exclusión y otra a partir de los factores primos, esta última es la siguiente:

\phi_{n} = n \cdot \prod_{d \in D}1 - \frac{1}{d}

Donde D es el conjunto de los primos que dividen a n.

Después de esto el resto de la fórmula se calcula fácilmente iterando por los divisores de acuerdo con la segunda fórmula del texto del problema.

Tercera Subtarea:

Podemos notar que la función es multiplicativa y calcularla con una criba lineal, para más detalle:

Explicación del problema

Tutorial relacionado con funciones multiplicativas y criba lineal.

Tutorial relacionado con mobius inversion.


Comments

There are no comments at the moment.