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

​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])