h2. Restricţii

* $1 ≤ t ≤ 10$

* $1 ≤ t ≤ 1000$

* $1 ≤ n ≤ 10^12^$

* Pentru $70%$ din teste $1 ≤ n ≤ 10^10^$.

* Pentru $70%$ din teste $1 ≤ n ≤ 10^10^$ şi $1 ≤ t ≤ 10$.

h2. Exemplu

O 'soluţie':job_detail/402347?action=view-source cu complexitatea <tex>O(T*\sqrt{N})</tex>, care parcurge numerele până la <tex>\sqrt{N}</tex> şi verifică dacă sunt divizori ai lui $N$, şi apoi se aplică formulele de mai sus ar trebui să obţină în jur de $70$ de puncte.

Având în vedere că numerele sunt până la $10^12^$, putem calcula toate numerele prime până la $10^6^$, cu ajutorul 'ciurului lui Eratosthenes':problema/ciur, iar pentru fiecare test se parcurg doar numerele prime până la <tex>\sqrt{N}</tex>, acestă 'soluţie':job_detail/467633?action=view-source obţinând $100$ de puncte.

Având în vedere că numerele sunt până la $10^12^$, putem calcula toate numerele prime până la $10^6^$, cu ajutorul 'ciurului lui Eratosthenes':problema/ciur, iar pentru fiecare test se parcurg doar numerele prime până la <tex>\sqrt{N}</tex>, acestă 'soluţie':job_detail/481606?action=view-source obţinând $100$ de puncte.

h3. Aplicaţii