2037 - Grea

Enunț

Vrăjitorul Arpsod are foarte multă treabă, așa că s-a gândit să vă ocupe timpul cu o problemă foarte grea, astfel încât acesta să poată lucra liniștit la proiectele sale despre stăpânirea lumii.

Acesta vă dă T numere naturale. Pentru fiecare număr A trebuie să găsiți cel mai mare K cu proprietatea că există un șir B de numere naturale nenule, nu neapărat distincte, astfel încât: (B1 + 1)(B2 + 1)...(BK + 1) = A

Cerinţa

Arătați-i vrăjitorului că problema nu e suficient de grea pentru voi, găsind numărul K cerut într-un timp cât mai scurt, pentru fiecare din cele T numere.

Date de intrare

Fișierul grea.in va conţine pe prima linie numărul natural T, reprezentând numărul de valori date. Urmează apoi T linii. Pe fiecare linie va exista un număr A, numărul dat de Arpsod.

Date de ieșire

Dacă datele sunt introduse corect, în fișier se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou fișierul grea.in va conţine pe prima linie numărul natural T, reprezentând numărul de valori date. Urmează apoi T linii. Pe fiecare linie va exista un număr A, numărul dat de Arpsod. În cazul în care datele nu respectă restricțiile, se va afișa in fișier : "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 1 ⩽ T ⩽ 500
• 2 ⩽ A ⩽ 2.000.000.000

Exemple

grea.in

1

4

grea.out

Datele sunt introduse corect.

2

Explicație

Ne interesează rezultatul pentru un număr (4) Şirul are 2 termeni: 1 şi 1 (1 + 1)(1 + 1) = 2 * 2 = 4

Rezolvare

<syntaxhighlight lang="python" line>

def validate(T, A_list):

   for a in A_list:
       if a < 2 or a > 2000000000:
           print("Datele nu corespund restrictițiilor impuse.")
           return False
   if T < 1 or T > 500:
       print("Datele nu corespund restrictițiilor impuse.")
       return False
   else:
       print("Datele introduse sunt corecte.")
   return True

def desc(n):

   cnt = 0
   d = 2
   while n > 1:
       p = 0
       while n % d == 0:
           n //= d
           p += 1
       cnt += p
       d += 1
       if d * d > n:
           d = n
   return cnt

if __name__ == '__main__':

   with open('grea.in', 'r') as fin:
       T = int(fin.readline().strip())
       A_list = [int(fin.readline().strip()) for _ in range(T)]

   if not validate(T, A_list):
       exit()

   with open('grea.out', 'w') as fout:
       for a in A_list:
           k = desc(a)
           fout.write(str(k) + '\n')

</syntaxhighlight>

Explicație rezolvare

În acest cod se implementează o funcție "desc" care primește un număr întreg pozitiv și returnează numărul de divizori primi ai acelui număr. Algoritmul folosit este numit "Cribă lui Eratostene" și presupune parcurgerea tuturor divizorilor primi ai numărului și numărarea acestora Funcția "validate" primește numărul T și o listă de numere A și verifică dacă acestea îndeplinesc condițiile cerute. În caz contrar, funcția afișează un mesaj corespunzător și returnează False. În cazul în care datele de intrare sunt valide, funcția returnează True. Blocul "main" începe prin citirea datelor de intrare din fișierul "grea.in". Dacă datele de intrare sunt invalide, programul se oprește. Altfel, se calculează pentru fiecare număr A din listă numărul de divizori primi folosind funcția "desc" și se scrie acest număr în fișierul de ieșire "grea.out". La final, am folosit condiția "if name == 'main':" pentru a asigura că blocul "main" este executat doar atunci când scriptul este rulat ca fișier principal și nu ca modul importat în alt script.