Sirgcdx

Observam ca forma generala unui sir gcd a bazat pe un sir b este :
a[ 1 ] = b[ 1 ]
a[ 2 ]} = divizor al lui a[ 1 ]
a[ 3 ] = divizor al lui a[ 2 ]
...
a[ n ] = divizor al lui a[ n-1 ].
Acest lucru este demonstrat de faptul ca a[i]=gcd(b[i],a[i-1]).
Orice sir de acest gen este generabil ca sir gcd(el se genereaza pe el insusi).
Prin urmare, orice sir gcd are forma de mai sus, iar orice sir cu forma de mai sus este sir gcd.

O solutie ce obtine 15 puncte este de a tine o dinamica O(n*k*k) - dp[i][j] - numarul de siruri de lungime i cu ultimul termen j.
Recurenta in O(k) - dp[i][j] = $$\sum_{ind = M_j}^{k} dp[i - 1][ind]
Aceasta recurenta poate fi implementata cu ciurul lui Eratostene,complexitatea devenind O(n*klogk) si obtinand 30 de puncte.

Fixam a1 intre 1 si k. Sigur restul numerelor se vor afla intre 1 si k.
La o analiza mai atenta,putem observa ca a[i] a[i-1] pentru putine pozitii(maxim log),deoarece daca a[i] != a[i-1],
atunci a[i] ≤ a[i-1] / 2 ( a[i] este divizor al lui a[i-1]).
Pentru a numara sirurile gcd,putem fixa numerele distincte ale sirului si pozitiile la care se modifica.
Pozitiile care se modifica le putem obtine din combinari de n-1 luate cate x,unde x este maxim log deci se pot calcula usor cu invers modular.
Pentru a calcula numerele distincte, avem 2 variante:

  1. O dinamica dp[i][j] - cate siruri de i numere distincte,cu fiecare divizor al precedentului, si cu ultimul termen j exista. i este maxim log in baza 2 din k si recurenta poate fi facuta cu pasii ca la ciurul lui Eratostene, deci complexitatea finala va fi O(k * log(k) * log(k)). Aceasta solutia obtine 50 sau 70 de puncte, in functie de modul de calcul a combinarilor.

O optimizare a acestei solutii ce duce la complexitatea O(klogk) si la 100 de puncte se poate face cu urmatoarea observatie:pe prima linie, au valori diferite de 0 numerele pana la k, pe a 2-a pana la k/2, pe a 3-a pana la k/8 (aceasta observatie este bazata pe cea de mai sus ($a[i] ≤ a[i-1]/2$)).
Astfel complexitatea se amortizeaza la klogk ( 1+1/2+1/4+..<2).

  1. Vom lucra independent pe factorii primi ai fiecarui numar de la 1 la k.
    Fie primul numar din sir x.
    Observam ca putem trata independent scaderea puterii unui factor prim al numarului x,deoarece factorii primi nu se influnteaza intre ei.
    Pentru fiecare putere posibila(maxim log in baza 2 din k) putem calcula in cate moduri o putem scadea de-a lungul a n-1 operatii(cu 0, 1 sau mai mult).
    Acest lucru se poate reliza calculand cateva combinari si avand o complexitate de maxim log3 k, dar fiind in precalculare, nu ne influenteaza complexitatea.
    Inmultim rezultatele pentru factorii primi si obtinem raspunsul.
    in final avem O(klogk) - fiecare numar are maxim logk factori primi,calculabili cu cirului lui Eratostene in O(k * log(log(k))), iar valorile pt fiecare factor prim sunt precalculate. Aceasta solutie obtine 100 de puncte. (in total sunt kloglogk factori, dar trebuie sa calculam pt fiecare puterea,fapt ce face complexitatea teoretica klogk dar in practica merge cel mai probabil sub acest numar de pasi).