McNugget

Cerință

Se dă un șir $v$ de $n$ numere naturale, un număr $k$ și $q$ query-uri. $x$-costul unei secvențe este numărul de numere distincte din secvență care apar de cel puțin $k$ ori în ea și au cel puțin un divizor comun cu $x$ diferit de $1$.

Se dau $q$ numere $x$, reprezentând query-urile. Pentru fiecare $x$ trebuie să aflați suma $x$-costurilor tuturor subsecvențelor din șir.

Date de implementare

Trebuie să implementați următoarea funcție:

std::vector<long long> solve(int n, int k, int q, std::vector<int> v, std::vector<int> x);

Această funcție trebuie să returneze răspunsul pentru cele $q$ interogări. Ea va fi apelată o singură dată la fiecare executare a programului. Observați că vectorul $v$ (șirul) este indexat de la $0$ la $n-1$ și vectorul $x$ (vectorul de query-uri) este indexat de la $0$ la $q-1$.

Nu uitați sa includeți header-ul mcnugget.h! De asemenea, nu uitați că nu trebuie să implementați funcția main, doar funcția solve.

Exemplu de grader

Un exemplu de grader citește $n, k, q$, șirul $v$ și șirul $x$. Apoi va apela $\text{solve}(n, k, q, v, x)$ și va afișa răspunsurile la ecran, fiecare pe câte o linie.

Restricții și precizări

• $1 \leq n, k \leq 10^5$;
• $1 \leq q, x_i, v_j \leq 10^6$, pentru $i$ de la $0$ la $q-1$ si $j$ de la $0$ la $n-1$;

Exemplu

stdin

4 1 2
6 6 5 9
10
5

stdout

13
6

Explicație

La primul query sunt $5$ secvențe cu $10$-costul egal cu $1$. Acestea sunt $[1,1]$, $[2,2]$, $[3,3]$, $[1,2]$, $[3,4]$. Sunt $4$ secvențe cu $10$-cost egal cu $2$: $[1,3]$, $[1,4]$, $[2,3]$, $[2,4]$. Observație: $cmmdc(6, 10) = 2 > 1$ și $cmmdc(5, 10) = 5 > 1$.

La al doilea query sunt $6$ secvențe cu $5$-cost egal cu $1$. Acestea sunt cele care îl conțin pe $5$ ($[1, 3]$, $[1, 4]$, $[2, 3]$, $[2, 4]$, $[3, 3]$, $[3, 4]$).