h1(#nambartiori). 'Soluţia':jc2020/solutii/nambartiori problemei 'Nambartiori':problema/nambartiori

h1(#nambartiori). 'Soluţia':jc2020/solutii/nambartiori problemei 'Nambartiori':problema/nambartiori
 
Notăm cu <tex>(x,y)</tex> cel mai mic divizor comun dintre <tex>x</tex> şi <tex>y</tex>. <tex>N</tex> şi <tex>k</tex> au semnificaţia din enunţ.
 
Cazul cu <tex>k = 2</tex> o sa îl tratăm separat. Se observă că orice două numere naturale <tex>a</tex> şi <tex>b</tex> cu <tex>a < b \le 2 * a</tex> formează o progresie geometrică validă, deoarece <tex>1 < \frac{a}{b} \le 2</tex>. Deci numărul de progresii geometrice care încep cu un număr <tex>a</tex> este chiar <tex>a</tex>.
Fie <tex>S(x)</tex> numărul de progresii geometrice de lungime <tex>2</tex> care încep cu un număr mai mic sau egal decât <tex>x</tex> şi au raţia între <tex>1</tex> şi <tex>2</tex>. Conform observaţiei de mai sus <tex>S(x) = 1 + 2 + ... + x = \frac{x*(x+1)}{2}</tex>. Putem afla prima poziţie din progresia geometrică cu o căutare binară în <tex>O(\log_{2}\sqrt n)</tex> sau cu o parcurgere simplă în <tex>O(\sqrt n)</tex>. Mai departe este foarte simplu să aflăm care este progresia cerută.
 
Fie <tex>p</tex> primul termen al unei progresii. Putem scrie raţia unei progresii ca <tex>\frac{a}{b}</tex>, unde <tex>b</tex> şi <tex>a</tex> sunt numere naturale prime între ele astfel încât <tex>b < a \le 2 * b</tex>.
Avem <tex>p * \frac{a}{b} = p + (\frac{(p * a - p * b)}{b}) = p + \frac{p * (a - b)}{b} = p + \frac{p * x}{b}</tex>. Cum <tex>b < a \le 2 * b => 0 < a - b \le b => 1 \le x \le b</tex>
În loc de a afla numărul de fracţii <tex>\frac{a}{b}</tex> putem afla numărul de fracţii de forma <tex>\frac{x}{b}</tex>, cu <tex>(x, b) = 1</tex> si <tex>x \le b</tex>, pentru că sunt echivalente conform demonstraţiei de mai sus.
Dacă vrem ca progresia să aibă <tex>k</tex> termeni, atunci ne interesează fracţiile pentru care numărul <tex>p * ( \frac{x}{b}) ^ {(k - 1)} </tex> este număr natural. Cum <tex>(x, b) = 1</tex>, proprietatea anterioară este echivalentă cu <tex>b ^ {k - 1}\ |\ p</tex>.
Rămâne să numărăm câte fracţii există. Pentru un <tex>b</tex> valid, <tex>x</tex> poate lua valori doar numere mai mici sau egale cu <tex>b</tex> astfel încât <tex>(x, b) = 1</tex>, deci numarul de fracţii este <tex>phi(b)</tex> (Indicatorul lui Euler).
 
Fie <tex>P(x)</tex> numărul de progresii geometrice de lungime <tex>k</tex> care încep cu <tex>x</tex> şi au raţia mai mare strict decât <tex>1</tex> şi mai mică sau egală cu <tex>2</tex>. Conform observaţiei de mai sus <tex>P(x) = \sum\nolimits_{} phi(b)</tex>, unde <tex>b^{k-1}\ |\ x</tex>.
Fie <tex>S(x)</tex> numărul de progresii geometrice de lungime <tex>k</tex> care încep cu un număr mai mic sau egal decât <tex>x</tex> şi au raţia între <tex>1</tex> şi <tex>2</tex>. Aşadar <tex>S(x) = \sum\limits_{i=1}^x P(i) </tex>. Dacă extindem suma obţinem <tex>S(x) = \sum\limits_{i=1}^x \sum\nolimits_{} phi(b)</tex>, unde <tex>b^{k-1}\ |\ i</tex>. Putem calcula suma rapid dacă aflăm pentru fiecare <tex>b</tex> de câte ori apare <tex>phi(b)</tex> în sumă. <tex>b</tex> poate lua valori până la <tex>\sqrt[k-1]x</tex>, iar <tex>phi(b)</tex> apare de <tex>\frac{x}{b^{k-1}}</tex> ori în sumă. Deci putem calcula <tex>S(x)</tex> în <tex>O(\sqrt[k-1]x)</tex>.  Căutăm binar prima valoare din progresie. Fie aceasta <tex>p</tex>. Fie <tex>B</tex> cel mai mare numar astfel încât <tex>B ^ {(k - 1)} | p</tex>. Observăm că <tex>P(x)</tex> poate fi scris ca <tex>\sum\nolimits_{b|B} phi(b)</tex>, dar această sumă este egală cu <tex>B</tex> deoarece <tex>\sum\nolimits_{d|n} phi(d)=n</tex>. Fie fracţiile <tex>\frac{1}{B}, \frac{2}{B}, ..., \frac{B}{B}</tex>. Numărul acestora este <tex>B</tex>, ele fiind distincte două câte două, iar pentru că <tex>p * (\frac{x}{B})^{(k-1)}</tex> este natural, înseamnă că progresiile geometrice valide care încep cu p sunt doar cele care au raţiile egale cu <tex>\frac{1}{B}, \frac{2}{B}, ..., \frac{B}{B}</tex>. Pe noi ne interesează <tex>a\ \ M-a</tex> progresie geometrică care începe cu <tex>p</tex>, unde <tex>M = N - S(p - 1)</tex>. Conform observaţiilor anterioare aceasta este <tex>p,p*\frac{M}{B},...p*(\frac{M}{B})^{(k-1)}</tex>. Complexitatea finală pentru a afla <tex>a\ \ n-a</tex> progresie geometrică de lungime <tex>k</tex> este <tex>O(\sqrt[k-1]n * \log_{2}n)</tex>.
 

private

protected