== include(page="template/taskheader" task_id="jupanul") ==

Pentru un sir de numere $a$, definim _costul_ ca fiind suma gcdurilor† tututor prefixelor lui $a$. De exemplu, costul sirului $[4, 4, 2, 1]$ este $gcd(4) + gcd(4, 4) + gcd(4, 4, 2) + gcd(4, 4, 2, 1) = 4 + 4 + 2 + 1 = 11$.

Pentru un sir de numere $a$, definim _costul_ ca fiind suma gcdurilor† tututor prefixelor lui $a$. De exemplu, costul sirului $[4,4,2,1]$ este $gcd(4) + gcd(4,4) + gcd(4,4,2) + gcd(4,4,2,1) = 4+4+2+1 = 11$.

Definim $f(n,k)$ ca fiind suma costurilor tuturor partitiilor lui $n$ in $k$ termeni‡.

Dandu-se $n$ si $m$, voi trebuie sa calculati $f(n, 1), f(n, 2),..., f(n, m)$

Dandu-se $n$ si $m$, voi trebuie sa calculati $f(n,1), f(n,2),...,f(n,m)$

† Prin $gcd(a{~1~}, a{~2~},..., a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~}, a{~2~},..., a{~i~}$.
‡ Prin o partitie a lui $n$ in $k$ termeni, intelegem un sir de numere pozitive $a{~1~}, a{~2~},..., a{~k~}$ cu proprietatea ca $a{~1~} · a{~2~}· ... · a{~k~}=n$

† Prin $gcd(a{~1~},a{~2~},...,a{~i~})$ s-a notat "cel mai mare divizor comun":https://en.wikipedia.org/wiki/Greatest_common_divisor al numerelor $a{~1~},a{~2~},...,a{~i~}$.
‡ Prin o partitie a lui $n$ in $k$ termeni, intelegem un sir de numere pozitive $a{~1~},a{~2~},...a{~k~}$ cu proprietatea ca $a{~1~}·a{~2~}·...·a{~k~}=n$

h2. Date de intrare

h2. Date de ieşire

Pe prima si singura linie a fisierului $jupanul.out$ se vor afla $f(n, 1), f(n, 2),..., f(n, m)$ separate prin exact un spatiu.

Pe prima si singura linie a fisierului $jupanul.out$ se vor afla $f(n,1), f(n,2),...,f(n,m)$ separate prin exact un spatiu.

h2. Restricţii

h2. Subtaskuri
table(restrictii). |_. # |_. Punctaj |_. Restricţii |

| $1$ | $10$ | $n ≤ 5\,000$ |
| $2$ | $20$ | $n ≤ 100\,000$ |

| $1$ | $10$ | $n ≤ 5000$ |
| $2$ | $20$ | $n ≤ 100000$ |

| $3$ | $10$ | $m ≤ 5$ |
| $4$ | $10$ | $n$ este o putere a unui numar prim |
| $5$ | $50$ | Fără restricţii suplimentare |

* {$[2, 3], cost = gcd($}{%{color:black}$[2$%}$]) + gcd([2, 3]) = 2 + 1 = 3$
* {$[3, 2], cost = gcd($}{%{color:black}$[3$%}$]) + gcd([3, 2]) = 3 + 1 = 4$

Deci $f(6, 2) = 2 + 7 + 3 + 4 = 16$

Deci $f(6,2)=2+7+3+4=16$

== include(page="template/taskfooter" task_id="jupanul") ==