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

<syntaxhighlight lang="python3"> def factorial(k):

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

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

Calcularea factorialului lui k

k_factorial = factorial(k)

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

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

Scrierea rezultatului în fișierul de ieșire

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

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

</syntaxhighlight>