2037 - Grea: Diferență între versiuni
Linia 8: | Linia 8: | ||
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. | 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 == | == Date de ieșire == | ||
Dacă datele sunt introduse corect, | |||
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 == | == Restricţii şi precizări == |
Versiunea curentă din 25 aprilie 2023 11:10
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.