Opis glavnog rešenja

Pomoću algoritma Eratostenovog sita možemo izračunati indikator \(I\) da li je neki broj prost ili ne u složenosti \(O(n \log \log n)\). Dalje možemo odrediti preslikavanje \(f\) koje prost broj \(p\) slika u par koordinata \((x, y)\), gde \(x\) i \(y\) resprektivno predstavljaju red i kolonu u kojoj se \(p\) nalazi u prostom trouglu.

Preslikavanje \(f\) konstruišemo iterativno prolazeći kroz sve interval \([2, n]\) održavajući trenutnu poziciju \((x, y)\) koju dodeljujemo sledećem prostom broju. Ukoliko je broj \(k\) koji se trenutno obrađuje prost, tj. važi \(I(k)\), onda \(f(k) \gets (x, y)\) i \((x', y') \gets (x, y + 1)\), tj. prelazimo na sledeću poziciju u istom redu. Ukoliko je broj \(k\) složen, tj. ne važi \(I(k)\), onda \((x', y') \gets (x, y)\). Kako konstruišemo trougao prostih brojeva mora da važi \(x \geq y\). Kako se \(x\) ne menja u iteracijama može se desiti da \(x\) postane manje od \(y\), tada znamo da treba preći u novi red, tj. \((x', y') \gets (x + 1, 1)\). Kako je svaka od iteracija konstantne složenosti, složenost konstruisanja preslikavanja \(f\) je \(O(n)\).

Pomoću indikatora \(I\) i preslikavanja \(f\) svaki upit možemo obraditi u konstantnoj složenosti. Ukupna složenost algoritma je tada \(O(n \log \log n + q)\).

#include <iostream>
#include <vector>

using namespace std;

vector<bool> sieve(const int n)
{
    vector<bool> is_prime(n + 1, true);

    is_prime[0] = false;
    is_prime[1] = false;

    for (int i = 2; i * i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * i; j <= n; j += i) {
                is_prime[j] = false;
            }
        }
    }

    return is_prime;
}

vector<pair<int, int>> calculate_mapping(const vector<bool> &is_prime, const int n)
{
    vector<pair<int, int>> res(n + 1);

    long row = 1, col = 1;
    for (int i = 2; i <= n; i++) {
        if (row < col) {
            row++;
            col = 1;
        }
        if (is_prime[i]) {
            res[i] = make_pair(row, col++);
        }
    }

    return res;
}

int main(void) 
{
    int n, q;
    cin >> n >> q;

    auto is_prime = sieve(n);
    auto mapping = calculate_mapping(is_prime, n);

    while (q--) {
        int num; 
        cin >> num;
        if (!is_prime[num]) {
            cout << -1 << endl;
        } else {
            auto [row, col] = mapping[num];
            cout << row << " " << col << endl;
        }
    }

    return 0;
}