2024 - Divizor 112

Cerinta

Se dă un şir format din n numere naturale nenule. Aflaţi cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

Date de intrare

Fișierul de intrare divizor112in.txt conține pe prima linie numărul n, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de iesire

Fișierul de ieșire divizor112out.txt va conține pe prima linie cel mai mic număr natural, diferit de 1, care divide un număr maxim de numere din şir.

Restrictii si precizari

• 1 ⩽ n ⩽ 100.000
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000

Exemplul 1

divizor112in.txt

5

1 2 3 4 5

divizor112out.txt

Datele introduse corespund restrictiilor impuse

2

Exemplul 2

divizor112in.txt

-4

1000001 64 -89 43580

divizor112out.txt

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python3" line="1"> def get_prime_factors(num):

   factors = {}
   divisor = 2
   while num > 1:
       while num % divisor == 0:
           num //= divisor
           factors[divisor] = factors.get(divisor, 0) + 1
       divisor += 1
   return factors

def find_max_divisor(nums):

   prime_factors_count = {}
   max_divisor = None
   max_count = 0

   for num in nums:
       factors = get_prime_factors(num)
       for factor, count in factors.items():
           prime_factors_count[factor] = max(prime_factors_count.get(factor, 0), count)

   for factor, count in prime_factors_count.items():
       if count > max_count:
           max_count = count
           max_divisor = factor

   return max_divisor

def verifica_restrictii(input_file, output_file):

   # Citire date de intrare
   with open(input_file, "r") as f:
       n = int(f.readline())
       numbers = list(map(int, f.readline().split()))

   # Apelare funcție de rezolvare
   result = find_max_divisor(numbers)

   # Verificare restricții
   if 1 <= n <= 100000 and all(1 <= num < 1000000 for num in numbers):
       # Citire rezultat așteptat
       with open(output_file, "r") as g:
           result_asteptat = int(g.readline().strip())

       # Verificare rezultat
       if result == result_asteptat:
           print("Rezultat corect!")
       else:
           print("Rezultat incorect!")
           print("Rezultat așteptat:", result_asteptat)
           print("Rezultat obținut:", result)
   else:
       print("Date de intrare nevalide!")

1. Citire date de intrare

with open("divizor112in.txt", "r") as f:

   n = int(f.readline())
   numbers = list(map(int, f.readline().split()))

1. Apelare funcție de rezolvare

result = find_max_divisor(numbers)

1. Scriere date de ieșire

with open("divizor112out.txt", "w") as g:

   g.write(str(result) + "\n")

1. Apelare funcție de verificare

verifica_restrictii("divizor112in.txt", "divizor112out.txt")

</syntaxhighlight>

Explicatie

2 divide două numere din şir.