Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2010-02-10 21:12:25.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ssnd.in, ssnd.outSursăArhiva educationala
AutorArhiva EducationalaAdăugată deMishu91Andrei Misarca Mishu91
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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 2 numere naturale, reprezentând răspunsul pentru fiecare din cele t întrebări.

Restricţii

  • 1 ≤ t ≤ 10
  • 1 ≤ n ≤ 1012

Exemplu

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

Explicaţie

Pentru 8, divizorii lui 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 \frac{p_{1}^{d_{1}+1}-1}{p_{1}-1}*\frac{p_{2}^{d_{2}+1}-1}{p_{2}-1}*...*\frac{p_{k}^{d_{k}+1}-1}{p_{k}-1}

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?