Question

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?”.

Cerința
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

Answer 1

#include<fstream>

#include<algorithm>

using namespace std;

int v[10001];

ifstream fin("divizori1.in");

ofstream fout("divizori1.out");

int n;

int f(int x){

int st = 1,dr = n;

while(st <= dr)

{

int mid = (st +dr)/2;

if(v[mid]>x)

dr = mid-1;

else if(v[mid] < x)

st = mid + 1;

else return mid;

}

return -1;

}

int main()

{

int q;

fin >> n >> q;

for(int i = 1;i<=n;i++)

{

fin >> v[i];

}

sort(&v[1],&v[n+1]);

int x;

for(int i = 0;i<q;i++)

{

fin >> x;

int div=0;

for(int j = 1;j<=x; j++){

if(x%j==0&&f(j)!=-1)

div++;

}

fout << div << "\n";

}

fout.close();

}