2031 - MDiv

Alexandru este elev în clasa a V-a și este foarte pasionat de informatică. Într-o zi acesta a descoperit un vector A cu N elemente și a început să se joace cu ele. Tatăl său, profesor de matematică, îi admiră ingeniozitatea și îi pune M întrebări de forma: “Câte valori din vectorul A sunt divizibile cu numărul x?”.

Cerința

Alexandru a rezolvat deja această problemă banală, așa că te provoacă și pe tine să o rezolvi!

Date de intrare

Fișierul de intrare mdiv.in conține pe prima linie numărul N. Pe a doua linie se află N numere naturale, reprezentând elementele vectorului. Pe a treia linie se află numărul M, iar pe următoarele M linii se află întrebările.

Date de ieșire

Fișierul de ieșire mdiv.out va conține M linii, pe linia i aflându-se răspunsul la întrebarea i.

Restricții și precizări

• 1 ≤ N, M ≤ 100.000
• fiecare valoare din vector, cât și fiecare întrebare ≤ 1.000.000 și sunt nenule.

Exemplu:

mdiv.in

8
2 4 2 6 1 9 1 5
3
2
5
3

mdiv.out

4
1
2

Explicație

Numerele divizibile cu 2 sunt 2, 4, 2, 6

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> ​n = 0 a = 0 x = [0] * 1000002 r = [0] * 1000002 m = 0 i = 0 o = 0 s = 0 mx = 0 with open("mdiv.intxt", "r") as fin:

   n = int(fin.readline())
   for i in range(1, n+1):
       a = int(fin.readline())
       if a > mx:
           mx = a
       x[a] += 1
   m = int(fin.readline())
   for i in range(1, m+1):
       a = int(fin.readline())
       if r[a] == 0:
           if a != 1:
               for o in range(0, mx+1, a):
                   r[a] += x[o]
           else:
               r[a] = n
       print(r[a])

</syntaxhighlight>