2342 - cadouri2

Cerința

După ce au trecut sărbătorile, ca în fiecare an, Moș Crăciun a început să facă inventarul cadourilor rămase pentru anul următor. El are N cadouri și pe fiecare cadou este scris un număr natural. În fiecare an Moș Crăciun trebuie să noteze într-un carnețel cantitatea de fericire pe care o aduc aceste cadouri copiilor.

Pentru a calcula această valoare, prima dată el trebuie să înmulțească toate numerele înscrise pe cele N cadouri. Astfel el obține un număr foarte mare. Apoi el știe că numărul de divizori al acestui număr este cantitatea de fericire pe care el trebuie să o scrie în carnețel. Ajutați-l pe Moș Crăciun să afle cantitatea de fericire a celor N cadouri. Deoarece acest număr este foarte mare voi trebuie sa aflați doar restul împărțirii la 1.000.000.007.

Date de intrare

Pe prima linie a fișierului de intrare cadouri2.in se află numărul natural N. Pe următoarea linie se află N numere naturale reprezentând numerele care sunt scrise pe cele N cadouri.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." In fișierul de ieșire cadouri2.out trebuie să se afle un singur număr care reprezintă cantitatea de fericire a celor N cadouri modulo 1.000.000.007

În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

1 ≤ N ≤ 1000
Numerele înscrise pe cadouri sunt numere naturale cuprinse între 1 și 106

Exemple

Exemplul 1

cadouri2.in: 3; 2 3 4
ecran: Datele sunt introduse corect.
cadouri2.out: 8

Exemplul 2

cadouri2.in: 5; 12 24 3 7 15
ecran: Datele sunt introduse corect.
cadouri2.out: 120

Exemplul 3

cadouri2.in: 5; 10000000 1 1 1 1
ecran: Datele nu corespund restricțiilor impuse.
cadouri2.out

Rezolvare

2342 - cadouri2

import math

Funcție pentru validarea datelor de intrare

def validate_input(n, a):

   if not (1 <= n <= 1000):
       return False
   if not all(1 <= x <= 10**6 for x in a):
       return False
   return True

Funcție pentru calcularea produsului factorilor primi ai tuturor numerelor și numărul de apariții a fiecărui factor prim

def calculate_factors(n, a):

   primes = []
   for i in range(2, int(math.sqrt(10**6)) + 1):
       if all(i % p != 0 for p in primes):
           primes.append(i)

   freq = [0] * len(primes)
   for num in a:
       for i in range(len(primes)):
           while num % primes[i] == 0:
               freq[i] += 1
               num //= primes[i]

   result = 1
   for f in freq:
       result = (result * (f + 1)) % 1_000_000_007

   return result

if __name__ == '__main__':

   # Citim datele de intrare din fișier
   with open('cadouri2.in', 'r') as f:
       n = int(f.readline().strip())
       a = list(map(int, f.readline().strip().split()))

   # Verificăm validitatea datelor de intrare
   if not validate_input(n, a):
       print("Datele nu corespund restricțiilor impuse.")
   else:
       print("Datele sunt introduse corect.")

       # Calculăm rezultatul și îl scriem în fișierul de ieșire
       with open('cadouri2.out', 'w') as g:
           g.write(str(calculate_factors(n, a))))

</syntaxhighlight>

Explicatie

calculate_factors(n, a): această funcție primește ca parametri un număr întreg n și un vector a de dimensiune n care conține numere naturale. Scopul acestei funcții este să calculeze produsul numărului de divizori ai fiecărui număr din vectorul a. Pentru a face acest lucru, funcția iterează prin fiecare element din vectorul a și calculează divizorii acelui număr. Acești divizori sunt stocați într-un dicționar care numără de câte ori apare fiecare divizor. La final, funcția calculează produsul dintre numărul de divizori pentru fiecare element și returnează rezultatul.

validate_input(n, a): această funcție primește ca parametri un număr întreg n și un vector a de dimensiune n care conține numere naturale. Scopul acestei funcții este să valideze datele de intrare și să verifice dacă respectă restricțiile impuse. Funcția verifică dacă n și fiecare element din vectorul a sunt numere naturale nenule, mai mici sau egale cu 10^6. De asemenea, funcția verifică dacă produsul elementelor din vectorul a este mai mic sau egal cu 10^9 sau 10^12, în funcție de valoarea lui n. Funcția returnează True dacă datele de intrare sunt valide și False în caz contrar.

main(): această funcție este funcția principală a programului. Ea deschide fișierul de intrare, citește datele de intrare și validează datele folosind funcția validate_input(). Dacă datele sunt invalide, funcția afișează un mesaj corespunzător și se oprește. Dacă datele sunt valide, funcția calculează produsul numărului de divizori folosind funcția calculate_factors(), apoi afișează rezultatul pe ecran și îl scrie în fișierul de ieșire.