== code(cpp) |Cnt[i][cmmdc(j, A[i])] = Cnt[i - 1][j] + Cnt[i - 1][cmmdc(j, A[i])]
==

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{@]@}$} (ultimele 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