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

Din descompunerea numărului în factori primi se pot calcula atât suma, cât şi numărul de divizori astfel: dacă <tex>n = p_{1}^{d_{1}}*p_{2}^{d_{2}}*...*p_{k}^{d_{k}}</tex>, atunci numărul de divizori este egal cu <tex>(d_{1}+1)*(d_{2}+1)*...*(d_{k}+1)</tex>, iar suma lor <tex>\dfrac{p_{1}^{d_{1}+1}-1}{p_{1}-1}*\dfrac{p_{2}^{d_{2}+1}-1}{p_{2}-1}*...*\dfrac{p_{k}^{d_{k}+1}-1}{p_{k}-1}</tex>. Pentru mai multe detalii puteţi consulta 'acest':http://www.google.ro/url?sa=t&source=web&ct=res&cd=2&ved=0CAsQFjAB&url=http%3A%2F%2Fwww.recreatiimatematice.ro%2Farhiva%2Fcomplementare%2FRM22002CRACIUN.pdf&rct=j&q=suma+divizorilor+unui+numar&ei=by5rS-i4LsWD4Qbrsuj5BQ&usg=AFQjCNEg2iowQL1rZib6pSN-J12y8p1siA&sig2=tcYBLSqWwFMgrALj5ySc6Q articol iar pentru formula sumei divizorilor consultaţi 'calcularea inversului modular':problema/inversmodular.

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.

O 'soluţie':job_detail/481608?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/402343?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