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