* Sumă din $[(N / 2 - i) / 2] - (i - 1)$, pentru $i$ de la $1$ la (N / 2) / 3, adică $N / 6$, unde $[A]$ reprezintă partea întreagă a lui $A$.

Această sumă se poate calcula destul de uşor.

Această sumă se poate calcula destul de uşor în O(1).

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.
 
 
*Solutie alternativa (mai simpla)*
 
Daca $N$ nu e divizibil cu $2^K^$ atunci raspunsul e $0$. In caz contrar, il impartim pe $N$ la $2^K^$ si astfel putem considera ca am plasat cate un $2$ in fiecare casuta. Il descompunem pe $N$ in factori primi. Daca un factor apare la puterea $X$, il putem plasa in casute in $comb(X+K-1,K-1)$ moduri.
 

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

protected

public