Doido Dev

Link do Problema Luogu CF1884D, Codeforces 1884D Tradução do Problema Dada uma sequência \(a\) de comprimento \(n\), um par \((i, j)\) com \(1 \leq i < j \leq n\) é considerado válido se não existir nenhum índice \(k\) (de 1 a \(n\)) tal que \(a_k\) divide \(a_i\) e \(a_k\) divide \(a_j\) simultaneamente. Calcule o número de pares válidos. A ...

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