Atenţie! Aceasta este ultima versiune a paginii, scrisă la 2020-05-30 14:56:14.
Revizia anterioară   Revizia următoare  

Soluţia problemei Nambartiori

Notăm cu (x,y) cel mai mic divizor comun dintre x şi y. N şi k au semnificaţia din enunţ.

Cazul cu k = 2 o sa îl tratăm separat. Se observă că orice două numere naturale a şi b cu a < b \le 2 * a formează o progresie geometrică validă, deoarece 1 < \frac{a}{b} \le 2. Deci numărul de progresii geometrice care încep cu un număr a este chiar a.
Fie S(x) numărul de progresii geometrice de lungime 2 care încep cu un număr mai mic sau egal decât x şi au raţia între 1 şi 2. Conform observaţiei de mai sus S(x) = 1 + 2 + ... + x = \frac{x*(x+1)}{2}. Putem afla prima poziţie din progresia geometrică cu o căutare binară în O(\log_{2}\sqrt n) sau cu o parcurgere simplă în O(\sqrt n). Mai departe este foarte simplu să aflăm care este progresia cerută.

Fie p primul termen al unei progresii. Putem scrie raţia unei progresii ca \frac{a}{b}, unde b şi a sunt numere naturale prime între ele astfel încât b < a \le 2 * b.
Avem p * \frac{a}{b} = p + (\frac{(p * a - p * b)}{b}) = p + \frac{p * (a - b)}{b} = p + \frac{p * x}{b}. Cum b < a \le 2 * b => 0 < a - b \le b => 1 \le x \le b
În loc de a afla numărul de fracţii \frac{a}{b} putem afla numărul de fracţii de forma \frac{x}{b}, cu (x, b) = 1 si x \le b, pentru că sunt echivalente conform demonstraţiei de mai sus.
Dacă vrem ca progresia să aibă k termeni, atunci ne interesează fracţiile pentru care numărul p * ( \frac{x}{b}) ^ {(k - 1)} este număr natural. Cum (x, b) = 1, proprietatea anterioară este echivalentă cu b ^ {k - 1}\ |\ p.
Rămâne să numărăm câte fracţii există. Pentru un b valid, x poate lua valori doar numere mai mici sau egale cu b astfel încât (x, b) = 1, deci numarul de fracţii este phi(b) (Indicatorul lui Euler).

Fie P(x) numărul de progresii geometrice de lungime k care încep cu x şi au raţia mai mare strict decât 1 şi mai mică sau egală cu 2. Conform observaţiei de mai sus P(x) = \sum\nolimits_{} phi(b), unde b^{k-1}\ |\ x.
Fie S(x) numărul de progresii geometrice de lungime k care încep cu un număr mai mic sau egal decât x şi au raţia între 1 şi 2. Aşadar S(x) = \sum\limits_{i=1}^x P(i) . Dacă extindem suma obţinem S(x) = \sum\limits_{i=1}^x \sum\nolimits_{} phi(b), unde b^{k-1}\ |\ i. Putem calcula suma rapid dacă aflăm pentru fiecare b de câte ori apare phi(b) în sumă. b poate lua valori până la \sqrt[k-1]x, iar phi(b) apare de \frac{x}{b^{k-1}} ori în sumă. Deci putem calcula S(x) în O(\sqrt[k-1]x). Căutăm binar prima valoare din progresie. Fie aceasta p. Fie B cel mai mare numar astfel încât B ^ {(k - 1)} | p. Observăm că P(x) poate fi scris ca \sum\nolimits_{b|B} phi(b), dar această sumă este egală cu B deoarece \sum\nolimits_{d|n} phi(d)=n. Fie fracţiile \frac{1}{B}, \frac{2}{B}, ..., \frac{B}{B}. Numărul acestora este B, ele fiind distincte două câte două, iar pentru că p * (\frac{x}{B})^{(k-1)} este natural, înseamnă că progresiile geometrice valide care încep cu p sunt doar cele care au raţiile egale cu \frac{1}{B}, \frac{2}{B}, ..., \frac{B}{B}. Pe noi ne interesează a\ \ M-a progresie geometrică care începe cu p, unde M = N - S(p - 1). Conform observaţiilor anterioare aceasta este p,p*\frac{M}{B},...p*(\frac{M}{B})^{(k-1)}. Complexitatea finală pentru a afla a\ \ n-a progresie geometrică de lungime k este O(\sqrt[k-1]n * \log_{2}n).