h2. 'Numar de Divizori':problema/ndiv

Se afla solutia pentru intervalul [1, A] si [1, B-1] 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 ... 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 2 pozitii consecutive in vectorul format si se aduna la solutie ( N / X1 ) * lungimea intervalului care este X2 - X1 + 1. 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] si [1, B-1] 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 ... 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 2 pozitii consecutive in vectorul format si se aduna la solutie ( N / X1 ) * lungimea intervalului care este X2 - X1 + 1. Complexitatea va fi O(sqrt(N)).