Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | nambartiori.in, nambartiori.out | Sursă | Junior Challenge 2020 |
| Autor | Cezar Trisca-Vicol | Adăugată de |  Comisia •JuniorChallenge2020 |
| Timp execuţie pe test | 0.08 sec | Limită de memorie | 524288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Nambartiori
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.
Cerinta
Stiind ca acesta si-a asezat banii in T progresii geometrice ajutati-l sa le gaseasca.
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 urmatoarele T linii, se vor găsi două numere n şi k, având semnificaţia din enunţ.
Date de ieşire
În fişierul de ieşire nambartiori.out se vor găsi T linii, pe fiecare linie i găsindu-se răspunsul la întrebarea i.
Restricţii
- T <= 10
- n <= 1.000.000.000
- 2 <= k <= 10
- Pentru 10 puncte k = 2
- Pentru alte 20 de puncte n <= 100
- Pentru alte 30 de puncte n <= 10.000
- Subtaskul 1 (20 puncte, testele 1-2): k = 2
- Subtaskul 2 (20 puncte, testele 3-4): n ≤ 100
- Subtaskul 3 (20 puncte, testele 5-6): n ≤ 10000
- Subtaskul 4 (40 puncte, testele 7-10): n ≤ 1000000000
Exemplu
| nambartiori.in | nambartiori.out |
|---|---|
| 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 | 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 |
Explicaţie
Primele 10 progresii geometrice de lungime 4 cu ratia ceruta 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
10 20 40 80
11 22 44 88
