# PBinfo #4604 – Macarie – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Macarie a primit o nouă temă la informatică, având următorul enunț: Se consideră un șir de numere naturale nenule, A cu N elemente. Fie șirul crescător D format din toți divizorii naturali, nu neapărat distincți, ai elementelor din A. De exemplu, pentru N = 4 și A = (6,2,3,2), avem șirul D = (1,1,1,1,2,2,2,3,3,6).

Cerința
Cunoscându-se un șir Poz format din Q numere naturale nenule, reprezentând poziții din șirul D să se determine, pentru fiecare dintre acestea, elementul corespunzător din șirul D.

Date de intrare
Pe prima linie a fișierului de intrare macarie.in se află numerele naturale N și Q. Pe a doua linie se află N numere naturale nenule, reprezentând, în ordine, termenii șirului A. Pe a treia linie se află Q numere naturale nenule, reprezentând, în ordine, elementele șirului Poz. Numerele aflate pe aceeași linie a fișierului de intrare sunt separate prin câte un spațiu.

Date de ieșire
Pe prima linie a fișierului de ieșire macarie.out se află Q numere naturale nenule, separate prin câte un spațiu, reprezentând elemente din D, în ordinea în care pozițiile lor apar în șirul Poz.

Restricții și precizări

1 ≤ N ≤ 1.000.000, 1 ≤ Q ≤ 100 000
Numerotarea elementelor în cadrul șirurilor A, D și Poz se face începând de la 1.
1 ≤ Ai ≤ 1.000.000 pentru 1 ≤ i ≤ N. Termenii șirului A nu sunt neapărat distincți.
1 ≤ Pozi ≤ |D| pentru 1 ≤ i ≤ Q, unde |D| este lungimea șirului D.
Datorită dimensiunilor mari, nu au fost adăugate toate testele.

Exemplul 1:
macarie.in

4 5
32 42 49 21
2 5 9 7 17
macarie.out

1 2 4 3 21
Explicație
N = 4 și Q = 5. A = (32,42,49,21) și D = (1,1,1,1,2,2,3,3,4,6,7,7,7,8,14,16,21,21,32,42,49). Pe pozițiile 2, 5, 9, 7, 17 din șir sunt valorile 1, 2, 4, 3, și 21

Exemplul 2:
macarie.in

5 4
24 56 8 490 28
35 25 28 38
macarie.out

70 12 14 490
Explicație
N = 5, Q = 4 și D[35] = 70, D[25] = 12, D[28] = 14, D[38] = 490.

## Cod sursă C++

```cpp
/// Sursa oficiala O(ValMax*log(ValMax) + Q*log(ValMax))
#include <fstream>
using namespace std;
ifstream f("macarie.in");
ofstream g("macarie.out");
const int NMAX = 1e6;
int C, N, M, Q;
int A[NMAX + 5];
int NrMultipli[NMAX + 5];
int cnt = 0;
struct lista
{
    int div, frecv;
};
lista Divizori[NMAX + 5];
void Precalculare()
{
    for (int i = 1; i <= N; ++i) /// NrMultipli[x] va retine pentru cate numere din sirul citit x este divizor
        NrMultipli[A[i]]++;      /// valorile din sir ul citit
    for (int d = 1; d <= NMAX; ++d)
        for (int j = 2 * d; j <= NMAX; j += d)
            NrMultipli[d] += NrMultipli[j];
    for (int i = 1; i <= NMAX; ++i)
        if (NrMultipli[i] != 0)
            Divizori[cnt].div = i, Divizori[cnt].frecv = NrMultipli[i], cnt++; /// creez lista divizori memorand {divizor,frecventa}
}
int main()
{
    f >> N >> Q;
    for (int i = 1; i <= N; ++i)
        f >> A[i];
    Precalculare();
    for (int i = 1; i < cnt; ++i)
        Divizori[i].frecv += Divizori[i - 1].frecv; /// sume partiale pe lista Divizorilor, a.i. Divizor[i].frecv este ultima
                                                    /// pozitie pe care apare i in lista divizorilor
    for (int i = 1; i <= Q; ++i)
    {
        int x = 0;
        f >> x;
        int st = 0, dr = cnt - 1;
        int pos = 0;
        while (st <= dr)
        { /// caut binar valoare divizorului aflat pe pozitia x
            int mij = (st + dr) / 2;
            if (x <= Divizori[mij].frecv)
            {
                dr = mij - 1;
                pos = mij;
            }
            else
                st = mij + 1;
        }
        g << Divizori[pos].div;
        if (i < Q)
            g << ' ';
        else
            g << '\n';
    }
    return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4604)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4604/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4604/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)