Fişierul intrare/ieşire:cuantictiori.in, cuantictiori.outSursăAutumn WarmUp 2020
AutorCezar Trisca-VicolAdăugată deautumnwarmup2020autumnwarmup2020 autumnwarmup2020
Timp execuţie pe test0.25 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Cuantictiori

O progresie geometrică de lungime k cu raţia r este un şir de numere naturale p(1),\ p(2),\  ... ,\ p(k) pentru care se respectă relaţia : p(i)\ =\ p(i-1)\ *\ r,\ 2 \le i \le k \hspace{0.1cm} , \hspace{0.1cm} r\hspace{0.1cm}\in\hspace{0.1cm}\mathbb{Q} \bigcap (1,2).

Se asigură că se poate demonstra că numărul de progresii geometrice de lungime k care au prima valoare egală cu N este egal cu cel mai mare număr natural X - 1 cu proprietatea că X^{k - 1} este divizor al lui N.

O progresie cuantică de lungime k cu raţia q este un şir de numere naturale p(1),\ p(2),\  ... ,\ p(k) pentru care se respectă relaţia : p(i)\ =\ p(i-1)\ ^{q},\ 2 \le i \le k \hspace{0.1cm} , \hspace{0.1cm} q \hspace{0.1cm}\in\hspace{0.1cm}\mathbb{Q} \bigcap (1,2).

Câte progresii cuantice distincte de lungime k au prima valoare între 2 şi N?

Date de intrare

Pe prima linie a fişierului de intrare se va afla numărul t de întrebări.
Pe următoarele t linii se vor afla câte 2 valori: n şi k cu semnificaţiile din enunţ.

Date de ieşire

În fişierul de ieşire se vor regăsi t valori pe t linii diferite.
Pe linia numărul i se va regăsi răspunsul la a i-a întrebare.

Restricţii

  •  t \le 10
  • k10
  • Subtask-ul 1 de 20 de puncte: n \le 10^{2}
  • Subtask-ul 2 de 40 de puncte: n \le 10^{6}
  • Subtask-ul 3 de 40 de puncte: n \le 10^{12}

Exemplu

cuantictiori.incuantictiori.out
3
30 2
149808 3
4230675774 3
10
24
282

Explicaţie

Primele 10 progresii cuantice de lungime 2 sunt:
4 8
8 16
8 32
9 27
16 32
16 64
16 128
25 125
27 81
27 243

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?