PrimeQuery_Ionescu

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long i64;
short n, ind, x;
vector<i64> v, numbers;
unordered_map<i64, short> pos;
vector<short> aib, afis;
i64 check[] {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41};
inline i64 Multiply(i64 a, i64 b, i64 MOD) {
    i64 res(0);
    while (b) {
        if (b & 1)
            res = (res + a) % MOD;
        a = (a + a) % MOD;
        b >>= 1;
    }
    return res;
}
inline i64 Powlog(i64 a, i64 b, i64 MOD) {
    i64 res(1);
    while (b) {
        if (b & 1)
            res = Multiply(res, a, MOD);
        a = Multiply(a, a, MOD);
        b >>= 1;
    }
    return res;
}
inline bool Test(i64 num, i64 baza) {
    i64 cn(num - 1), exponent(0);
    while (cn % 2 == 0)
        ++exponent, cn >>= 1;
    i64 x = (num - 1) / (1ULL << exponent), pw = Powlog(baza, x, num);
    if (pw == 1 || pw == num - 1)
        return true;
    for (i64 i = 1; i < exponent; ++i) {
        pw = Powlog(pw, 2, num);
        if (pw == num - 1)
            return true;
    }
    return false;
}
inline bool Prim(i64 x) {
    if (x < 2) return false;
    if (x == 2) return true;
    if (x % 2 == 0) return false;
    bool ok(false);
    for (int k = 0; k < 12 && !ok; ++k)
        if (x == check[k])
            ok = true;
    if (!ok) {
        ok = true;
        for (int k = 0; k < 12 && ok; ++k)
            ok = Test(x, check[k]);
    }
    return ok;
}
inline void Update(int pos) {
    for (int i = pos; i <= ind; i += i & -i)
        ++aib[i];
}
inline int Query(int pos) {
    int sum(0);
    for (int i = pos; i > 0; i -= i & -i)
        sum += aib[i];
    return sum;
}
int main() {
    ios_base::sync_with_stdio(false);
    ifstream fin("primequery.in");
    fin >> n;
    v = numbers = vector<i64>(n);
    for (int i = 0; i < n; ++i) {
        fin >> v[i];
        numbers[i] = v[i];
    }
    fin.close();
    sort(numbers.begin(), numbers.end());
    numbers.erase(unique(numbers.begin(), numbers.end()), numbers.end());
    for (const i64& x : numbers)
        pos[x] = ++ind;
    aib = vector<short>(ind + 1);
    for (int i = 0; i < n; ++i) {
        x = pos[v[i]];
        afis.emplace_back(Query(x - 1));
        if (Prim(v[i]))
            Update(x);
    }
    ofstream fout("primequery.out");
    for (const short& x : afis)
        fout << x << ' ';
    fout.close();
    return 0;
}