bazaf

Bazaf

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

În matematică factorialul unui număr natural nenul K este notat cu K! şi este egal cu produsul numerelor naturale nenule mai mici sau egale cu K.

În matematică factorialul unui număr natural nenul $K$ este notat cu {$K$}! şi este egal cu produsul numerelor naturale nenule mai mici sau egale cu {$K$}.

<tex>1! = 1; \: 2! = 1 \cdot 2 = 2; \: 3! = 1 \cdot 2 \cdot 3 = 6,....,K! = 1 \cdot 2 \cdot 3 \cdot ... \cdot K. </tex>

De exemplu: $1! = 1; 2! = 1 * 2 = 2; 3! = 1 * 2 * 3 = 6; ...; K! = 1 * 2 * 3 * ... * K$

Orice număr natural N poate fi descompus cu ajutorul numerelor factoriale astfel:

Orice număr natural $N$ poate fi descompus cu ajutorul numerelor factoriale astfel:

<tex> N= 1! \cdot f_1 + 2! \cdot f_2 + 3! \cdot f_3 + ... + m! \cdot f_m </tex>

$N = 1! * f{~1~} + 2! * f{~2~} + 3! * f{~3~} + ... + m! * f{~m~}$

unde coeficienţii f{~i~}, cu 1≤i≤m sunt numere naturale şi în plus f{~m~} ≠0;

unde coeficienţii $f{~i~}$, cu $1 ≤ i ≤ m$ sunt numere naturale şi în plus $f{~m~} ≠ 0$;

<tex> 20=1! \cdot 20; \: 20=1! \cdot 6+2! \cdot 4+3! \cdot 1; \: 20 =1! \cdot 0+2! \cdot 1+3! \cdot 3 </tex>

De exemplu: $20 = 1! * 20 = 1! * 6 + 2! * 4 + 3! * 1 = 1! * 0 + 2! * 1 + 3! * 3$

intre toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condiţiile 0 ≤ f{~i~} ≤i, cu 1≤ i <m şi 0< f{~m~} ≤m.

Între toate aceste descompuneri posibile există o singură descompunere, numită descompunere în bază factorială care respectă suplimentar condiţiile $0 ≤ f{~i~} ≤ i$, cu $1 ≤ i < m$ şi $0 < f{~m~} ≤ m$.

<tex> 6=1! \cdot 0+2! \cdot 0+3! \cdot 1; \: 17 =1! \cdot 1+2! \cdot 2+3! \cdot 2; \: 119 =1! \cdot 1+2! \cdot 2+3! \cdot 3+4! \cdot 4 </tex>

De exemplu: $6 = 1! * 0 + 2! * 0 + 3! * 1; 17 = 1! * 1 + 2! * 2 + 3! * 2; 119 = 1! * 1 + 2! * 2 + 3! * 3 + 4! * 4$

h2. Cerinţe

1.Să se determine descompunerea în bază factorială a unui număr natural X dat.
2.Cunoscând o descompunere oarecare a unui număr natural Y să se determine descompunerea în baza factorială a acestuia.

1. Să se determine descompunerea în bază factorială a unui număr natural X dat.
2. Cunoscând o descompunere oarecare a unui număr natural Y să se determine descompunerea în baza factorială a acestuia.

h2. Date de intrare

Acesta conţinepe primul rând un număr natural V care poate avea doar valorile 1 sau 2 cu următoarea semnificaţie:
* dacă valoarea lui V este 1, pe a doua linie a fişierului de intrare se găseşte un număr natural X cu semnificaţia de mai sus;

 
* dacă valoarea lui V este 2, pe a doua linie a fişierului de intrare se găseşte o descompunere a unui număr Y sub forma unui şir de valori naturale în care primul termen este m, urmat de m valori f{~i~} , care respectă condiţiile f{~i~} ≥0 , cu 1≤i<m şi f{~m~} ≠0, despărţite prin câte un spaţiu, cu semnificaţia de mai sus.

* dacă valoarea lui V este 2, pe a doua linie a fişierului de intrare se găseşte o descompunere a unui număr Y sub forma unui şir de valori naturale în care primul termen este $m$, urmat de $m$ valori f{~i~} , care respectă condiţiile f{~i~} ≥0 , cu 1≤i<m şi f{~m~} ≠0, despărţite prin câte un spaţiu, cu semnificaţia de mai sus.

h2. Date de ieşire
Fişierul de ieşire este $bazaf.out$.

Dacă valoarea V este 1, atunci fişierul de ieşire va conţine descompunerea în baza factorialăa numărului X iar dacă valoarea V este 2, atunci fişierul de ieşire va conţine descompunerea în baza factorială a numărului Y. Descompunerea în bază factorială presupune scrierea în fişierul de ieşire a unei singure linii sub forma unui şir de valori naturale în care primul termen este m, urmat de mv alori f{~i~} , care respectă condiţiile 0≤ f{~i~} ≤i, cu 1≤ i<m şi 0 < f{~m~} ≤ m, despărţite prin câte un spaţiu, având semnificaţia de mai sus.

Dacă valoarea $V$ este $1$, atunci fişierul de ieşire va conţine descompunerea în baza factorială a numărului $X$ iar dacă valoarea $V$ este $2$, atunci fişierul de ieşire va conţine descompunerea în baza factorială a numărului {$Y$}. Descompunerea în bază factorială presupune scrierea în fişierul de ieşire a unei singure linii sub forma unui şir de valori naturale în care primul termen este {$m$}, urmat de $m$ valori f{~i~} , care respectă condiţiile $0 ≤ f{~i~} ≤ i$, cu $1 ≤ i < m$ şi $0 < f{~m~} ≤$ $m$, despărţite prin câte un spaţiu, având semnificaţia de mai sus.

h2. Restricţii

* <tex> 2 \leq X \leq 10^{15} </tex>
* <tex> 1 \leq m \leq 100000 </tex>
* <tex> 0 \leq f_i \leq 10^9 </tex>

* $2 ≤ X ≤ 1.000.000.000.000.000$
* $1 ≤ m ≤ 100.000$
* $0 ≤ f{~i~} ≤ 1.000.000.000$

h2. Exemplu