Fişierul intrare/ieşire:	desc.in, desc.out	Sursă	preONI 2006 Runda 2
Autor	Adrian Diaconu	Adăugată de
Timp execuţie pe test	0.25 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	4/5

Vezi solutiile trimise | Statistici

Descompuneri

Se defineste o descompunere a unui numar natural N ca fiind o secventa crescatoare ( nu neaparat stricta ) de numere naturale al caror produs este N

Cerinta

Dandu-se un numar natural N si un numar natural K calculati numarul de descompuneri ale lui N precum si cea de-a K -a descompunere a sa(in ordine lexicografica).

Date de Intrare

Prima linie a fisierului de intrare desc.in contine doua numere intregi N , respectiv K cu semnificatia de mai sus.

Date de Iesire

In fisierul desc.out veti afisa pe prima linie X numarul de descompuneri ale lui N , iar pe a doua linie veti afisa sirul care reprezinta cea de-a K -a descompunere, numerele fiind despartite printr-un spatiu.

Restrictii si precizari

• 1 ≤ N ≤ 10¹²
• 1 ≤ K ≤ 10⁹
• Un sir A₁, A₂,...,A_s este mai mic lexicografic decat un alt sir B₁, B₂,...,B_t daca exista i ≤ min(s,t) astfel incat A₁=B₁, A₂=B₂,...,A_i-1=B_i-1 si A_i < B_i
• Pentru fiecare test se se vor acorda 4 puncte pentru aflarea corecta a numarului de descompuneri, si 6 puncte pentru aflarea celei de-a K-a descompunere.

Exemplu

Explicatii

Cele 9 descompuneri sunt (in ordine lexicografica): 2 2 3 3 , 2 2 9 , 2 3 6 , 2 18 , 3 3 4 , 3 12 , 4 9 , 6 6 , 36

Cum se trimit solutii?