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

1

n = 0

a = 0

x = [0] * 1000002

r = [0] * 1000002

m = 0

i = 0

o = 0

s = 0

mx = 0

with open("mdiv.in", "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])