1596 - Divizori 1

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 divizori1.in 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).