1596 - Divizori 1

From Bitnami MediaWiki

Cerinţa

Fie X un vector de numere naturale distincte, de dimensiune N, X = (x[1], x[2], …, x[N]). Se dă un număr natural Q, apoi Q întrebări de forma: “Câţi divizori ai lui Qi se află în şirul X?”. Răspundeţi la cele Q întrebări.

Date de intrare

Fișierul de intrare divizori1in.txt conține:

  • Pe prima linie 2 numere N și Q, reprezentând dimensiunea lui X şi numărul de întrebări;
  • Pe a doua linie se găsesc N numere separate prin spaţiu, reprezentând elementele vectorului X.
  • Pe următoarele Q linii se găsesc cele Q întrebări, reprezentate printr-un număr Qi pe fiecare linie.

Date de ieșire

Fișierul de ieșire divizori1.out va conține:

  • Q linii, fiecare linie i, reprezentând răspunsul pentru Qi.

Restricţii şi precizări

  • 1 ⩽ N, Q ⩽ 10.000
  • 1 ⩽ Qi, Xi ⩽ 100.000

Exemplu

divizori1.in
5 2
6 2 3 12 4
6
12
divizori1.ou
3
5

Rezolvare

<syntaxhighlight lang="python" line>

  1. Deschidem fișierul de intrare și citim datele

with open('divizori1.in', 'r') as fin:

   n, q = map(int, fin.readline().split())
   x = list(map(int, fin.readline().split()))
   queries = [int(fin.readline()) for _ in range(q)]
  1. Inițializăm lista de răspunsuri

answers = []

  1. Parcurgem fiecare întrebare

for query in queries:

   # Calculăm numărul de divizori ai lui query care se află în x
   answer = sum(1 for xi in x if query % xi == 0)
   # Adăugăm răspunsul la lista de răspunsuri
   answers.append(answer)
  1. Scriem răspunsurile în fișierul de ieșire

with open('divizori1.out', 'w') as fout:

   for answer in answers:
       fout.write(str(answer) + '\n')

</syntaxhighlight>

Explicatie

  • 6 conţine 3 divizori în şir(6, 2, 3)
  • 12 conţine 5 divizori în şir(6, 2, 3, 12, 4).