h2. Date de ieşire

În fişierul de ieşire $ssnd.out$ se vor afla $t$ linii, fiecare linie conţinând 2 numere naturale, reprezentând răspunsul pentru fiecare din cele $t$ întrebări.

În fişierul de ieşire $ssnd.out$ se vor afla $t$ linii, fiecare linie conţinând câte două numere naturale, reprezentând răspunsurile pentru fiecare din cele $t$ întrebări.

h2. Restricţii

* $1 ≤ t ≤ 10$

* $1 ≤ t ≤ 1000$

* $1 ≤ n ≤ 10^12^$

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

h2. Exemplu
table(example). |_. ssnd.in |_. ssnd.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
8
12
13
| 4 15
6 28
2 14

|
h3. Explicaţie

...

Divizorii lui $8$ sunt $1$, $2$, $4$, $8$, iar suma lor este $1+2+4+8 = 15$.
Divizorii lui $12$ sunt $1$, $2$, $3$, $4$, $6$, $12$, iar suma lor este $1+2+3+4+6+12 = 28$.
$13$ este număr prim, prin urmare are doar $2$ divizori, pe $1$ şi pe el însuşi, iar suma lor este $14$.
 
h3. Indicaţii de rezolvare
 
O 'soluţie':job_detail/402331?action=view-source brută, care parcurge toate numerele de la $1$ la $n$ şi numără toţi divizorii ar trebui să obţină aproximativ $30$ de puncte.
 
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/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/481606?action=view-source obţinând $100$ de puncte.
 
h3. Aplicaţii
 
* 'Suma divizorilor':problema/sumdiv

== include(page="template/taskfooter" task_id="ssnd") ==

4580