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>