Funções Multiplicativas e Inversão de Möbius

Pré-requisito - Blocagem de Divisão Problema Dado um número $ n $, calcule: $$ \sum_{i=1}^n \lfloor \frac{n}{i} \rfloor $$ Abordagem e Código Este somatório pode ser calculado em tempo $ \mathcal{O}(n) $. Para otimizar, observe que para valores grandes de $ n $, muitas frações $ \lfloor n/i \rfloor $ terão o mesmo valor. Por exemplo, para $ n ...

Publicado em 7-11 20:35