题意：求\(1 - N(1\le N \le 1e18)\)中，能表示成\(M^k(M>0,k>1)\)的数的个数
分析：正整数p可以表示成\(p = m^k = m^{r*k'}\)的形式，其中k'为素数。枚举幂k，求出满足\(p^k\le N\)的最大的\(p\),则对于当前的\(k\),任意小于\(p\)的正整数\(p'\)，都有\(p'^{k}<N\)，因此在\(1-N\)范围内有\(N^{\frac{1}{k}}\)个满足条件的数。
因为\(2^{60}>10^{18}\)，所以枚举到的k'最多不超过60，预处理出60以内的所有素数。
又\(2*3*5=30,2*3*5*7=210>60\)，所以最多只考虑3个素幂次相乘的情况。
但是如此枚举会出现重复的情况，例如\((2^{3})^{2} = (2^{2})^{3} = 2^6\)在枚举\(k=2\)和\(k=3\)时重复了，根据容斥的思想，枚举到偶数个素幂次相乘时，减去该结果。
*注意每次计算\(N^{\frac{1}{k}}\)时，减去1的情况，最后将结果加1，因为1在每种情况中都会出现，不必重复。
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn = 1e5+5;
const LL prime[20] ={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59};
const int len = 17;
const double eps =1e-8;
LL ans;
LL N;
void dfs(int pos,int num,int tot,LL k = 1)
{
if(k>60) return;
if(num==tot){
LL p = (LL)(pow(N,1.0/(0.0+k))+eps)-1;
ans +=p;
return;
}
if(pos==len) return;
dfs(pos+1,num,tot,k);
dfs(pos+1,num+1,tot,k*prime[pos]);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
while(scanf("%lld",&N)==1){
LL res= 0;
for(int i =1;i<=3;++i){
ans=0;
dfs(0,0,i);
if(i&1) res+=ans;
else res-=ans;
}
res+=1;
printf("%lld\n",res);
}
return 0;
}