题目分析:
这种题目标题写莫比乌斯反演会不会显得太恐怖了，那就容斥算了。
gcd不为1的肯定可以开根。所以把根式结果算出来就行了。
辣鸡题目卡我精度。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const long long LMAX = 9223372036854775807; 5 6 long long n; 7 int mu[100]; 8 9 void init(){ 10 for(int i=2;i<=70;i++){ 11 int p = i; 12 mu[i] = -1; 13 for(int j=2;j*j<=p;j++){ 14 int cnt = 0; while(p%j == 0) p/=j,cnt++; 15 if(cnt != 1 && cnt != 0) mu[i] = 0; 16 else if(cnt == 1) mu[i]*=-1; 17 } 18 if(p != 1) mu[i]*=-1; 19 } 20 } 21 22 long long fast_pow(int now,int pw){ 23 long long ans = 1,dt = now; 24 int bit = 1; 25 while(bit <= pw){ 26 if(bit & pw){ 27 if(ans < LMAX/dt) ans *= dt; 28 else ans = LMAX; 29 } 30 if(dt < LMAX/dt) dt *= dt; 31 else dt = LMAX; 32 bit<<=1; 33 } 34 return ans; 35 } 36 37 void work(){ 38 long long ans = 0; 39 for(int i=2;i<=70;i++){ 40 if(mu[i] == 0) continue; 41 int z = pow((long double)n,1.0/(long double)i); 42 if(z == 1) break; 43 if(fast_pow(z,i) > n) z--; 44 if(fast_pow(z+1,i) <= n) z++; 45 z--; ans += z*mu[i]; 46 } 47 n -= ans;n--; 48 printf("%I64d\n",n); 49 } 50 51 int main(){ 52 int Tmp; scanf("%d",&Tmp); 53 init(); 54 while(Tmp--){ 55 scanf("%I64d",&n); 56 work(); 57 } 58 return 0; 59 }