Pagini recente » Heapuri | Suma și numărul de divizori

Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-02-27 19:30:17.
Revizia anterioară Revizia următoare

Fişierul intrare/ieşire:	ssnd.in, ssnd.out	Sursă	Arhiva educationala
Autor	Arhiva Educationala	Adăugată de	Andrei Misarca •Mishu91
Timp execuţie pe test	0.05 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Suma si numarul divizorilor

Divizorii unui număr natural n reprezintă mulţimea de numere naturale, mai mici sau egale cu n, cu proprietatea că divid pe n. Să se determine pentru t numere naturale cardinalul acestei mulţimi şi restul împărţirii sumei elementelor mulţimii la 9973.

Date de intrare

Fişierul de intrare ssnd.in conţine pe prima linie un număr natural t. Pe următoarele t linii se va afla câte un număr natural n.

Date de ieşire

Î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.

Restricţii

1 ≤ t ≤ 10
1 ≤ n ≤ 10¹²
Pentru 70% din teste 1 ≤ n ≤ 10¹⁰.

Exemplu

ssnd.in	ssnd.out
3 8 12 13	4 15 6 28 2 14

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.

Indicaţii de rezolvare

O soluţie 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ă $n = p_{1}^{d_{1}}*p_{2}^{d_{2}}*...*p_{k}^{d_{k}}$ , atunci numărul de divizori este egal cu $(d_{1}+1)*(d_{2}+1)*...*(d_{k}+1)$ , iar suma lor $\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}$ . Pentru mai multe detalii puteţi consulta acest articol iar pentru formula sumei divizorilor consultaţi calcularea inversului modular.

O soluţie cu complexitatea $O(T*\sqrt{N})$ , care parcurge numerele până la $\sqrt{N}$ ş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¹², putem calcula toate numerele prime până la 10⁶, cu ajutorul ciurului lui Eratosthenes, iar pentru fiecare test se parcurg doar numerele prime până la $\sqrt{N}$ , acestă soluţie obţinând 100 de puncte.

Aplicaţii

Suma divizorilor

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content

infoarena informatica de performanta