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.