description
\(10^5\) 次询问
每次给定 \(n\leq 10^{18}\), 求 2 到 \(n\) 内质因子分解结果为 \(p_{a_1}^{b_1}p_{a_2}^{b_2}...\)，且 \(\gcd(b1,b2...)=1\) 的数的个数。
solution
显然答案为 \(\sum\limits_{i=1} \mu(i) \lfloor\sqrt[i]{n}-1\rfloor\)。
直接用 cmath 里的 pow 计算的话精度会炸掉。
手写二分会 TLE。
建议先用 pow 得到 \(n\) 的 \(i\) 次方根的粗略取值，然后微调，用快速幂判断（中间如果发现返回值已经大于 \(n\) 了直接返回）。
具体见代码吧。qwq
hint
计算浮点数下取整一定不能忽略精度问题。
code
#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const int N=100;
ll n,miu[100],pw[N][N];
bool chk(ll a,ll b,ll L){
ll ret=1;
while(b){
if(b&1) ret=ret*a;
if(ret>L) return false;
a=a*a;
b>>=1;
}
return true;
}
void solve(){
long long t1;
cin>>t1;
n=t1;
ll v=0,ans=0;
for(int i=1; ; i++){
ll v=pow(n,1.0/i);
while(chk(v,i,n)) v++;
while(!chk(v,i,n)) v--;
v--;
if(v==0) break;
ans=ans+miu[i]*v;
}
cout<<(long long)ans<<endl;
}
/// 100000000000000000
vector<ll> primes;
int st[111];
int main(){
// . .. . 省略了预处理mobius函数 .. . //
int T;
cin>>T;
while(T--) solve();
return 0;
}