Fişierul intrare/ieşire:jap.in, jap.outSursăAlgoritmiada 2009, Runda 2
AutorBogdan-Cristian TataroiuAdăugată debogdan2412Bogdan-Cristian Tataroiu bogdan2412
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Jap

J. Tamplaru' are de rezolvat urmatoarea problema pentru ora de mate:

Sa se determine numarul de elemente distincte generate de secventa ab (a la puterea b), pentru a, b numere intregi cu 1 ≤ a ≤ N si 1 ≤ b ≤ M.

Tatal sau, G. Tamplaru' I, s-a uitat peste tema fiului sau si dupa ce a aflat de existenta informaticii cand isi construia biroul in problema trecuta, s-a hotarat sa va dea voua problema sa o rezolvati pentru diverse valori ale lui N si M.

Date de intrare

Fişierul de intrare jap.in contine pe prima linie numarul T de teste. Urmatoarele T linii contin pe fiecare linie cate 2 numere naturale N si M cu semnificatiile de mai sus.

Date de ieşire

Fişierul de ieşire jap.out va contine T linii, cate una pentru fiecare test din intrare.

Restricţii

  • 1 ≤ T ≤ 10 000
  • 1 ≤ N, M ≤ 100 000
  • 20% din testele folosite la evaluare vor avea T = 1 si 1 ≤ N, M ≤ 1 000
  • 70% din testele folosite la evaluare vor avea T ≤ 100
  • Important Numarul de valori diferite ale lui M din fisierul de intrare nu va fi mai mare de 30

Exemplu

jap.injap.out
2
5 5
2 2
19
3

Explicatie

Pentru exemplul al doilea secventa generata este formata din elementele 11 = 1, 12 = 1, 21 = 2, 22 = 4. Numarul de elemente distincte din aceasta secventa este 3.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content