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

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')

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.