Nambartiori

nambartiori

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

$K0kalaru47$ şi-a dat seama că singurul mod de a face mulţi bani în viaţă este de a învăţa matematică. Dupa ce a studiat îndelungat tainele matematicii, acesta a ajuns la concluzia că "Nambăr Tiori" este capitolul lui preferat. Îi place atât de mult incât acesta a început în fiecare zi să îşi aşeze banii în grămezi astfel încât dacă ar scrie pe o foaie numărul de bani din fiecare grămadă, şirul rezultat ar fi o progresie geometrică de numere naturale. O progresie geometrică de lungime $k$ cu raţia $r$ este un şir de numere $p(1), p(2), ..., p(k)$ pentru care se respectă relaţia: $p(i) = p(1) * r^i - 1^, 2 ≤ i ≤ k$. Din păcate, el fiind un k0kalar adevărat, nu ţine cont de bani, iar după ce i-a aşezat într-o progresie geometrică a uitat numărul lor. Tot ce ţine minte despre progresia geometrică este că e a $N$-a progresie geometrica de lungime $k$ cu raţia mai mare decât $1$ şi mai mică sau egală cu $2$ în ordine lexicografică.
 
 
h2. Cerinţă
 
Ştiind că acesta şi-a aşezat banii în $T$ progresii geometrice ajutaţi-l să le gasească.

Kokalaru' 47 si-a dat seama ca singurul mod de a face multi bani in viata este de a invata matematica. Dupa ce a studiat indelungat tainele matematicii, acesta a ajuns la concluzia ca "Nambăr Tiori" este capitolul lui preferat. Ii place atat de mult incat acesta a inceput in fiecare zi sa isi aseze banii in gramezi astfel incat daca ar scrie pe o foaie numarul de bani din fiecare gramada, sirul rezultat ar fi o progresie geometrica de numere naturale. O progresie geometrica de lungime k cu ratia r este un sir de numere $p(1), p(2), ..., p(k)$ pentru care se respecta relatia : $p(i) = p(1) * r ^ (i - 1) , 2 <= i <= k$. Din pacate, el fiind un kokalar adevarat, nu tine cont de bani, iar dupa ce i-a asezat intr-o progresie geometrica a uitat numarul lor. Tot ce tine minte despre progresia geometrica este ca e a n-a progresie geometrica de lungime k in ordine lexicografica, iar ratia ei este mai mare decat $1$ si mai mica sau egala cu $2$.
Stiind ca acesta si-a asezat banii in T progresii geometrice ajutati-l sa gaseasca progresiile geometrice.

h2. Date de intrare

Fişierul de intrare $nambartiori.in$ conţine pe prima linie un număr natural $T$, reprezentând numărul de teste. Pe următoarele $T$ linii, se vor găsi două numere $n$ şi $k$, având semnificaţia din enunţ.

Fişierul de intrare $nambartiori.in$ conţine pe prima linie un număr natural $T$, reprezentând numărul de teste. Pe urmatoarele $T$ linii, se vor găsi două numere $n$ şi $k$, având semnificaţia din enunţ.

h2. Date de ieşire

h2. Restricţii
* $T <= 10$

* $n <= 1.000.000.000$

* $p <= 1.000.000.000$

* $2 <= k <= 10$

 
h2. Subtaskuri
 
* $**Subtaskul 1 (10 puncte, testul 1):**$ $k = 2$
* $**Subtaskul 2 (20 puncte, testele 2-3):**$ $n ≤ 100$
* $**Subtaskul 3 (30 puncte, testele 4-6):**$ $n ≤ 10.000$
* $**Subtaskul 4 (40 puncte, testele 7-10):**$ $Restricţiile iniţiale$

* Pentru $10$ puncte $k = 2$
* Pentru alte $20$ de puncte $n <= 100$
* Pentru alte $30$ de puncte $n <= 10.000$

h2. Exemplu
table(example). |_. nambartiori.in |_. nambartiori.out |

| 10

| 15
10 2

1 4
2 4
3 4

8 4
9 4
10 4

| 1 2 4 8

11 4
12 4
845689 6
1065354 4
| 4 8
1 2 4 8

2 4 8 16
3 6 12 24
4 8 16 32

8 12 18 27
8 16 32 64
9 18 36 72

|
| 5
5763 2
34568 7
9345 3
845689 6
1065354 4
| 107 199
33922 67844 135688 271376 542752 1085504 2171008
3105 6210 12420

10 20 40 80
11 22 44 88

810280 1620560 3241120 6482240 12964480 25928960

783083 1566166 3132332 6264664

783083 1566166 3132332 6264664

|

h3. Explicaţie

Primele $10$ progresii geometrice de lungime $4$ cu raţia cerută sunt :
$1 2 4 8$
$2 4 8 16$
$3 6 12 24$
$4 8 16 32$
$5 10 20 40$
$6 12 24 48$
$7 14 28 56$
$8 12 18 27$
$8 16 32 64$
$9 18 36 72$

...

== include(page="template/taskfooter" task_id="nambartiori") ==