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, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou afișează 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.

În caz contrar, se va afișa pe ecran: "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 validare_date(T, A_list):

   for a in A_list:
       if a < 2 or a > 2000000000:
           return False
   if T < 1 or T > 500:
       return False
   else:
       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 validare_date(T, A_list):
       fout.write("Datele nu corespund restrictițiilor impuse.")
       exit()

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

</syntaxhighlight>

Explicație rezolvare

Funcția validate(T, A_list) verifică dacă datele din fișierul de intrare corespund restricțiilor impuse . Dacă datele nu corespund, funcția va returna False și se va afișa mesajul "Datele nu corespund restrictițiilor impuse.".
Funcția desc(n) calculează numărul de factori primi ai unui număr n dat pentru a putea găsi numarul cerut K. Algoritmul este următorul: se împarte n la toți factorii primi mai mici sau egali cu radicalul pătrat al lui n (acesta este cel mai mare factor prim posibil), numărând de fiecare dată câte divizori primi ai lui n se împart la fiecare factor prim găsit. Apoi, se crește d la următorul număr prim și se repetă procesul până când d * d > n. În final, se adaugă numărul de divizori primi găsiți la un contor și se returnează acesta. În funcția main, fișierul de intrare "grea.in" este deschis, se citesc T și A_list, iar apoi se verifică dacă datele sunt corecte utilizând funcția validate(T, A_list). Dacă datele sunt corecte, se deschide fișierul de ieșire "grea.out" și se calculează K pentru fiecare A din A_list, apoi se afișează numărul K în fișierul de ieșire. Dacă datele nu sunt corecte, programul se va opri cu mesajul "Datele nu corespund restrictițiilor impuse." în fișierul de ieșire.