题意：
给定n，问有多少个p=m^k,满足p<=n（要求m>=1，k>1）
数据范围：n<=1e18
解法：
显然枚举m肯定不行,因为m^2<=1e18,那么m<=1e9,
考虑枚举k,2^60>1e18,因此枚举k最多枚举60个,如果k是一个合数,那么k可以拆分为一个数与质数的乘积:k=x*p,
那么m^k可以变为m^(x*p)=(m^x)^p,
因此k只需要枚举质数即可
x^p<=n,那么(x-1)^p也一定<=n,因此x的数量为n^(1/p),累加至答案即可但是这样会有重复,例如(x^3)^5和(x^5)^3,所以但需要减去x^(3*5)
最后的式子应该是cal(x^p1)+cal(x^p2)-cal(x^(p1*p2))+cal(...)
即加上指数为一个指数的,减掉指数有两个质数的,然后还要再加回指数有3个指数的.
理论上还要减掉4个指数,加上5个指数...但是2*3*5*7>60,因此指数的质数个数不超过3,最多容斥到3个质数ps:
m=1的情况单独考虑,容斥的时候不计算m=1的情况,最后答案再加上1参考:
https://blog.csdn.net/ramay7/article/details/51908666
code：
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxm=65;
const double eps=1e-8;
int prime[maxm],cnt;
int n;
int ans;
int isprime(int x){for(int i=2;i*i<=x;i++){if(x%i==0)return 0;}return 1;
}
void init(){for(int i=2;i<=60;i++){if(isprime(i)){prime[cnt++]=i;}}
}
void dfs(int cur,int sum,int num){//cur是prime[]指针,sum是指数,num是素数个数if(sum>60)return ;if(cur==cnt){//搜完了if(num<1)return ;int temp=(int)(pow(n,1.0/sum)+eps)-1;//-1是因为要把m=1的情况减掉if(num&1)ans+=temp;else ans-=temp;return ;}dfs(cur+1,sum,num);//当前素数不选dfs(cur+1,sum*prime[cur],num+1);//当前素数选
}
signed main(){init();while(cin>>n){ans=0;dfs(0,1,0);cout<<ans+1<<endl;//+1是因为要把m=1的情况加回来}return 0;
}