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 |
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 ≤ 1012
- 1 ≤ K ≤ 109
- Un sir A1, A2,...,As este mai mic lexicografic decat un alt sir B1, B2,...,Bt daca exista i ≤ min(s,t) astfel incat A1=B1, A2=B2,...,Ai-1=Bi-1 si Ai < Bi
- 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
desc.in | desc.out |
---|---|
36 5 | 9 3 3 4 |
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