2332 - primXXL

Cerința

Se dau n numere naturale şi un număr natural k. Aflaţi câte dintre numerele date îl divid pe k! ( k factorial).

Date de intrare

Fișierul de intrare primxxl.in conține pe prima linie numerele n şi k, iar pe a doua linie n numere naturale nenule separate prin spații.

Date de ieșire

Fișierul de ieșire primxxl.out va conține pe prima linie numărul d, reprezentând numărul numerelor de pe a doua linie a fișierului de intrare care îl divid pe k!.

Restricții și precizări

1 ≤ n ≤ 10.000 1 ≤ k ≤ 1.000.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000.000 Exemplu: primxxl.in

3 5 20 3 14 primxxl.out

2

Explicație

Avem k!=5!=120, iar dintre numerele date 20 şi 3 îl divid pe 120, deci două numere.

Rezolvare

def factorial(k):

   result = 1
   for i in range(2, k + 1):
       result *= i
   return result

1. Citire date de intrare

with open("primxxl.in", "r") as file:

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

1. Calcularea factorialului lui k

k_factorial = factorial(k)

1. Numărarea câtor dintre numerele date îl divid pe k!

count = sum(1 for num in numbers if k_factorial % num == 0)

1. Scrierea rezultatului în fișierul de ieșire

with open("primxxl.out", "w") as file:

   file.write(str(count) + "\n")