antidivizor

Algoritmul, pas cu pas

Nu putem calcula $F(k)$ pentru fiecare $k$ separat: $N$ urcă până la $10^{15}$, iar $T$ poate fi $10^5$. Trebuie o formulă care dă suma direct.

Pleacă de la definiție. $F(k)$ e cel mai mic număr care nu divide $k$. Asta înseamnă că toate numerele mai mici, $1, 2, \dots, F(k)-1$, divid pe $k$. Iar $1, 2, \dots, m$ divid simultan pe $k$ exact când cel mai mic multiplu comun al lor divide pe $k$: $1, 2, \dots, m \mid k \iff \text{lcm}(1, 2, \dots, m) \mid k$

Notăm $L_m = \text{lcm}(1, 2, \dots, m)$. Atunci $F(k) - 1$ e cel mai mare $m$ pentru care $L_m \mid k$, deci putem număra: $F(k) = 1 + \#\{m \ge 1 : L_m \mid k\}$