h2. 'Numar de Divizori':problema/ndiv

Se afla solutia pentru intervalul $[1, A-1]$ si $[1, B]$ si se face diferenta. Pentru un interval $[1, N]$ si un numar $X$, se afla numarul de numere din interval care se divid la $X$ prin aflarea catului $N / X$. O simpla solutie ar fi pentru fiecare $X = 1 2 ... N$ se face suma lui $N / X$. Evident nu intra in timp. Daca se scrie sirul $N/X$ cu $X$ de la $1$ la $N$ se observa ca termenii sirului sunt in ordine descrescatoare. De exemplu sa vedem pentru $N = 12$, vom avea sirul $N/X$ : $12/1$, $12/2$, $12/3$ ... $12/12$ care este $12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1$. Solutia se bazeaza pe faptul ca aceste numere se repeta pe anumite intervale. Astfel se iau toate numerele $i$ de la $1$ la $sqrt(N)$ si se vor tine intr-un vector sortate valorile: $i$ si $N/i$. Acum pentru doua pozitii consecutive in acest vector vom avea doua valori: $X1$ si $X2$ si $N/X1$ = $N/X2$. Si orice numar din intervalul $[X1, X2]$, sa zicem $Y$ va avea $N/Y$ = $N/X1$. Acum se iau toate pozitiile consecutive in vectorul format si se aduna la solutie $(N/X1)*(X2-X1+1)$ (lungimea intervalului). Corectitudinea acestei solutii se bazeaza pe faptul ca daca ar fi sa imparti numarul $N$ la toate numerele de la $1$ la $N$, se obtin $2*sqrt(N)$ diferite caturi. De exemplu nu poti sa imparti $12$ la ceva mai mic egal cu $12$ si sa obtii catul $11$. Complexitatea va fi $O(sqrt(N))$.

Se afla solutia pentru intervalul $[1, A-1]$ si $[1, B]$ si se face diferenta. Pentru un interval $[1, N]$ si un numar $X$, se afla numarul de numere din interval care se divid la $X$ prin aflarea catului $N / X$. O simpla solutie ar fi pentru fiecare $X = 1 2 ... N$ se face suma lui $N/X$. Evident nu intra in timp. Daca se scrie sirul $N/X$ cu $X$ de la $1$ la $N$ se observa ca termenii sirului sunt in ordine descrescatoare. De exemplu sa vedem pentru $N = 12$, vom avea sirul $N/X$ : $12/1$, $12/2$, $12/3$ ... $12/12$ care este $12, 6, 4, 3, 2, 2, 1, 1, 1, 1, 1, 1$. Solutia se bazeaza pe faptul ca aceste numere se repeta pe anumite intervale. Astfel se iau toate numerele $i$ de la $1$ la $sqrt(N)$ si se vor tine intr-un vector sortate valorile: $i$ si $N/i$. Acum pentru doua pozitii consecutive in acest vector vom avea doua valori: $X1$ si $X2$ si $N/X1$ = $N/X2$. Si orice numar din intervalul $[X1, X2]$, sa zicem $Y$ va avea $N/Y$ = $N/X1$. Acum se iau toate pozitiile consecutive in vectorul format si se aduna la solutie $(N/X1)*(X2-X1+1)$ (lungimea intervalului). Corectitudinea acestei solutii se bazeaza pe faptul ca daca ar fi sa imparti numarul $N$ la toate numerele de la $1$ la $N$, se obtin $2*sqrt(N)$ diferite caturi. De exemplu nu poti sa imparti $12$ la ceva mai mic egal cu $12$ si sa obtii catul $11$. Complexitatea va fi $O(sqrt(N))$.