1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154
| #include <iostream> #include <sstream> #include <iomanip> #include <algorithm> #include <set> #include <map> #include <queue> #include <stack> #include <vector> #include <string> #include <cstring> #include <cmath> #include <cstdio> #define all(v) (v).begin(), (v).end() #define unq(v) (v).erase(unique(all(v)), (v).end()) #define ii int, int #define li int, int #define ll2 ll, ll #define vec vector #define pii pair <int, int> #define pli pair <ll, int> #define pll2 pair <ll, ll> #define mp make_pair #define pb push_back #define fi first #define se second #define MULTI int T; cin >> T; while(T--) #define sqr(x) ((x) * (x)) #define test cerr << '!' << endl; using namespace std; typedef long long ll; typedef unsigned long long ull; int main0 (); int main () { #ifndef ONLINE_JUDGE freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin); #endif ios::sync_with_stdio(false); clock_t start, end; main0(); #ifndef ONLINE_JUDGE fclose(stdin); #endif return 0; } const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1}; const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1}; const int INF = 0x3f3f3f3f; const ll INFF = 0x3f3f3f3f3f3f3f3f; const int mod = 998244353; const double eps = 1e-6; const double Pi = acos(-1.0); const int N = 5e6 + 2; bool np[N]; int prime[N], pi[N]; int getprime() { int cnt = 0; np[0] = np[1] = true; pi[0] = pi[1] = 0; for(int i = 2; i < N; ++i) { if(!np[i]) prime[++cnt] = i; pi[i] = cnt; for(int j = 1; j <= cnt && i * prime[j] < N; ++j) { np[i * prime[j]] = true; if(i % prime[j] == 0) break; } } return cnt; } const int M = 7; const int PM = 2 * 3 * 5 * 7 * 11 * 13 * 17; int phi[PM + 1][M + 1], sz[M + 1]; void init() { getprime(); sz[0] = 1; for(int i = 0; i <= PM; ++i) phi[i][0] = i; for(int i = 1; i <= M; ++i) { sz[i] = prime[i] * sz[i - 1]; for(int j = 1; j <= PM; ++j) phi[j][i] = phi[j][i - 1] - phi[j / prime[i]][i - 1]; } } int sqrt2(ll x) { ll r = (ll)sqrt(x - 0.1); while(r * r <= x) ++r; return int(r - 1); } int sqrt3(ll x) { ll r = (ll)cbrt(x - 0.1); while(r * r * r <= x) ++r; return int(r - 1); } ll getphi(ll x, int s) { if(s == 0) return x; if(s <= M) return phi[x % sz[s]][s] + (x / sz[s]) * phi[sz[s]][s]; if(x <= prime[s]*prime[s]) return pi[x] - s + 1; if(x <= prime[s]*prime[s]*prime[s] && x < N) { int s2x = pi[sqrt2(x)]; ll ans = pi[x] - (s2x + s - 2) * (s2x - s + 1) / 2; for(int i = s + 1; i <= s2x; ++i) ans += pi[x / prime[i]]; return ans; } return getphi(x, s - 1) - getphi(x / prime[s], s - 1); } ll getpi(ll x) { if(x < N) return pi[x]; ll ans = getphi(x, pi[sqrt3(x)]) + pi[sqrt3(x)] - 1; for(int i = pi[sqrt3(x)] + 1, ed = pi[sqrt2(x)]; i <= ed; ++i) ans -= getpi(x / prime[i]) - i + 1; return ans; } ll lehmer_pi(ll x) { if(x < N) return pi[x]; int a = (int)lehmer_pi(sqrt2(sqrt2(x))); int b = (int)lehmer_pi(sqrt2(x)); int c = (int)lehmer_pi(sqrt3(x)); ll sum = getphi(x, a) +(ll)(b + a - 2) * (b - a + 1) / 2; for (int i = a + 1; i <= b; i++) { ll w = x / prime[i]; sum -= lehmer_pi(w); if (i > c) continue; ll lim = lehmer_pi(sqrt2(w)); for (int j = i; j <= lim; j++) sum -= lehmer_pi(w / prime[j]) - (j - 1); } return sum; } int main0 () { init(); MULTI { ll n; cin >> n; ll k = lehmer_pi(n) - lehmer_pi(n / 2) + 1; cout << n - (n - k) / 2 << endl; } }
|