RT，不知道为什么 TLE 了qwq

代码：

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef unsigned long long ull;

const int N = 1e9 + 7, M = 7, P = 1 << (M - 1), Q = (N >> M) + 7, R = 6;
int addition[R + 7] = {0, 4, 0, 0, 0, 2};
ull a[Q], sum[Q];

inline int pop_count(ull n){
	int ans = 0;
	while (n){
		n &= n - 1;
		ans++;
	}
	return ans;
}

inline void init(){
	int t = sqrt(N - 1);
	for (register int i = 9; i < N; i += 6){
		int x = (i - 3) >> M, y = ((i - 3) >> 1) & (P - 1);
		a[x] |= 1ull << y;
	}
	for (register int i = 5; i <= t; i += addition[i % R]){
		int u = (i - 3) >> M, v = ((i - 3) >> 1) & (P - 1);
		if (!(a[u] & (1ull << v))){
			int i_mul_2 = i * 2;
			for (register int j = i * i; j < N; j += i_mul_2){
				int x = (j - 3) >> M, y = ((j - 3) >> 1) & (P - 1);
				a[x] |= 1ull << y;
			}
		}
	}
	for (register int i = 0; i < Q; i++){
		sum[i] = sum[i - 1] + pop_count(~a[i]);
	}
}

inline int get_nth_prime(int n){
	n -= 2;
	if (n == -1) return 2;
	int x = lower_bound(sum, sum + Q, n) - sum, y = sum[x], ans = P * (x + 1);
	for (register int i = P - 1; i >= 0; i--){
		if (!(a[x] & (1ull << i)) && --y == n) return ((ans - 1) << 1) + 3; 
		ans--;
	}
}

int main(){
	int q;
	cin >> q;
	init();
	for (register int i = 1; i <= q; i++){
		int k;
		cin >> k;
		cout << get_nth_prime(k) << endl;
	}
	return 0;
}