Sprim
Fie A[i] vectorul citit. Consideram pentru fiecare pozitie i vectorul P[i] pozitia cea mai din dreapta pana in pozitia i, astfel incat A[i] nu e prim cu A[P[i]]. Vrem sa calculam S[i] = pozitia unde incepe subsecventa maximala (ce respecta conditiile din enunt) care contine i pe ultima pozitie. Raspunsul este suma tuturor i - S[i] cu 1 ≤ i ≤ N.
Presupunem ca avem calculat S[i-1] si vrem sa calculam S[i]. Se observa doua conditii necesare si suficiente pentru S[i]:
- S[i] > P[i] (e clar ca subsecventa care contine i nu poate sa treaca sau sa contina P[i] pentru ca astfel nu se respecta conditia)
- S[i] ≥ S[i-1] (trebuie ca subsecventa care contine i sa nu treaca mai departe de subsecventa care contine i-1 pentru ca iar nu se respecta conditia)
De aici rezulta ca S[i] = max(S[i-1], P[i] + 1). Tot ce ramane de calculat este P[i] si dupa aceea S[i] se poate calcula secvential de la 1 la N.
Pentru a calcula P[i] eficient vom proceda in felul urmator: ca sa stim cea mai din dreapta pozitie pana in i astfel incat A[i] nu e prim cu A[P[i]] ne intereseaza cel mai din dreapta numar care contine un factor prim al lui A[i]. Aceasta este usor de facut tinand un vector cu ultima aparitie al fiecarui factor prim pana la pozitia i. P[i] va fi maximul dintre ultimele pozitii ale factorilor primi ai numarului A[i]. Dupa ce terminam de procesat numarul A[i] modificam vectorul cu aparitiile factorilor primi ai lui A[i] cu pozitia i.
Aveti grija la descompunerea numerelor in factori primi. Pentru a lua punctaj maxim se recomanda incercarea secventiala a fiecarui numar prim pana in sqrt(A[i]).
