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

Vezi solutiile trimise

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 ≤ 1000
  • 1 ≤ n ≤ 1012
  • Pentru 70% din teste 1 ≤ n ≤ 1010 şi 1 ≤ t ≤ 10.

Exemplu

ssnd.inssnd.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 1012, putem calcula toate numerele prime până la 106, 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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content