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ă.

Kokalaru47 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$ cu ratia mai mare decat $1$ si mai mica sau egala cu $2$ in ordine lexicografica.

h2. Cerinţă

h2. Cerinta

Ştiind că acesta şi-a aşezat banii în $T$ progresii geometrice ajutaţi-l să le gasească.

Stiind ca acesta si-a asezat banii in $T$ progresii geometrice ajutati-l sa le gaseasca.

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

* $T <= 10$
* $n <= 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 1 (10 puncte, testele 1-2):**$ $k = 2$
* $**Subtaskul 2 (20 puncte, testele 3-4):**$ $n ≤ 100$
* $**Subtaskul 3 (30 puncte, testele 5-6):**$ $n ≤ 10.000$

* $**Subtaskul 4 (40 puncte, testele 7-10):**$ $Restricţiile iniţiale$
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

10 20 40 80
11 22 44 88
810280 1620560 3241120 6482240 12964480 25928960
783083 1566166 3132332 6264664
|
| 15
10 2
1 4
2 4
3 4
4 4
5 4
6 4
7 4
8 4
9 4
10 4
11 4
12 4

845689 6
1065354 4

| 107 199
33922 67844 135688 271376 542752 1085504 2171008
3105 6210 12420

|
| 4 8
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
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 :

Primele $10$ progresii geometrice de lungime $4$ cu ratia ceruta sunt :

$1 2 4 8$
$2 4 8 16$
$3 6 12 24$

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

$10 20 40 80$
$11 22 44 88$

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