h1. 'Tot o luna':problema/totoluna

Ne putem imagina că vrem să împărţim numărul $N$ în $K$ căsuţe. În fiecare căsuţă se va afla un număr par, iar produsul numerelor din căsuţe trebuie să fie egal cu $N$. Având în vedere că în fiecare căsuţă trebuie să existe un număr par, va trebui să avem cel puţin un factor de $2$ în fiecare căsuţă. Prin urmare, dacă numărul $N$ nu are cel puţin $K$ factori de $2$ în descompunerea sa, răspunsul va fi $0$. Acum urmează să aranjăm aceşti factori de $2$ din descompunerea lui $N$, fie ei $F2$, în cele $K$ căsuţe, astfel încât să existe cel puţin un factor de $2$ în fiecare căsuţă. Altfel spus, va trebui să determinăm numărul de moduri în care $F2$ poate fi scris ca sumă de exact $K$ numere naturale, mai mari sau egale cu $1$. Pentru aceasta, ne putem folosi de metoda programării dinamice:
 
* $d1[i][j] = numărul de posibilităţi în care poţi scrie j, ca sumă de i numere naturale mai mari sau egale decât 1.$
 
Vom pregenera această matrice pentru a putea aşeza rapid factorii de $2$ din scrierea lui $N$, pentru fiecare query în parte.
 
Acum, urmează să aşezăm restul factorilor din descompunerea în factori primi ai lui $N$. Procedeul va fi asemenea cu cel prezentat până acum. De această dată însă, nu suntem interesaţi ca fiecare căsuţă în parte din cele $K$ să conţină cel puţin un factor din cei rămaşi. De aceea, putem pregenera o matrice cu o semnificaţie asemănătoare:
 
* $d0[i][j] = numărul de posibilităţi în care poţi scrie j, ca sumă de i numere naturale mai mari sau egale decât 0.$
 
Având aceste informaţii disponibile, pentru fiecare query, vom descompune numărul $N$ în factori primi, urmând să calculăm răspunsul folosindu-ne de aceste două matrici, pentru fiecare factor prim în parte şi puterea la care acesta apare.
 

h1. 'Subsecvente':problema/subsecvente
==include(page="template/monthly-2014/footer")==