题目链接：http://codeforces.com/contest/1036/problem/F
题意：
题解：求在[2,n]中,x != a ^ b（b >= 2 即为gcd）的个数，那么实际上就是要求x = a ^ b的个数，然后用总数减掉就好了，答案即为
。（pow会丢失精度，学习避免精度丢失的方法）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define mp(a,b) make_pair(a,b)
#define pi acos(-1)
#define pii pair<int,int>
#define pb push_back
const int INF = 0x3f3f3f3f;
const double eps = 1e-;
const int MAXN = 1e5 + ;
const int MAXM = 2e6 + ;
const ll mod = 1e9 + ; bool check[];
int prime[];
int mu[]; void Moblus(int N) {
mst(check, false);
mu[] = ;
int tot = ;
for(int i = ; i <= N; i++) {
if(!check[i]) {
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot; j++) {
if(i * prime[j] > N) {
break;
}
check[i * prime[j]] = true;
if(i % prime[j] == ) {
mu[i * prime[j]] = ;
break;
} else {
mu[i * prime[j]] = -mu[i];
}
}
}
} int main()
{
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
Moblus();
int t;
scanf("%d",&t);
while(t--) {
ll n;
scanf("%lld",&n);
ll ans = ;
for(int i = ; i <= ; i++) {
if(!mu[i]) continue;
ll raiz = round(pow(n, 1.0 / i));
while(pow((long double)raiz, i) > (long double)n) raiz--;
while(pow((long double)raiz + , i) <= (long double)n) raiz++;
raiz--;
ans += (ll)mu[i] * raiz;
}
printf("%lld\n",n - + ans);
}
return ;
}