h4. Solutia 1

Prima solutie, si cea mai simpla, utilizeaza principiul programarii dinamice. Se calculeaza numarul de subsiruri din primele i elemente care sunt divizibile cu un numar j intre 1 si 1000. Sa notam acest numar cu Cnt(i, j). Se obtine urmatoare recurenta pentru calculul acestor valori:

Prima solutie, si cea mai simpla, utilizeaza principiul programarii dinamice. Se calculeaza numarul de subsiruri din primele $i$ elemente care sunt divizibile cu un numar $j$ intre $1$ si {$1000$}. Sa notam acest numar cu {$Cnt{@[@}i{@][@}j{@]@}$}. Se obtine urmatoare recurenta pentru calculul acestor valori:

Cnt(i, cmmdc(j, Ai)) = Cnt(i - 1, j) + Cnt(i - 1, cmmdc(j, Ai))

== code(cpp) |$Cnt(i, cmmdc(j, Ai)) = Cnt(i - 1, j) + Cnt(i - 1, cmmdc(j, Ai))$
==

Odata calculate aceste valori solutia o vom avea in Cnt(N, 1). Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei 10 este periculoasa, pe unele teste fiind necesar folosirea bazei 10^9 pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula Cnt(i, j) ne sunt necesare doar valorile pentru Cnt(i - 1, k) (ultima doua linii). Complexitatea acestei solutiei va fi O(N * K * L) unde K reprezinta valoarea maxima din sir si L lungimea maxima a numerelor mari.

Odata calculate aceste valori solutia o vom avea in {$Cnt{@[@}N{@][@}1{@]@}$}. Numerele depasesc orice tip de date predefinit si trebuie utilizate numere mari. Limitele fiind destul de mari, folosirea bazei $10$ este periculoasa, pe unele teste fiind necesar folosirea bazei $10^9^$ pentru a reduce timpul de executie. De asemenea si memoria se poate reduce, observand faptul ca pentru a calcula {$Cnt{@[@}i{@][@}j{@]@}$} ne sunt necesare doar valorile pentru {$Cnt{@[@}i-1{@][@}k{@]@}$} (ultima doua linii). Complexitatea acestei solutiei va fi $O(N * K * L)$ unde $K$ reprezinta valoarea maxima din sir si $L$ lungimea maxima a numerelor mari.

h4. Solutia 2