Description
求第k个没有完全平方因子的数,k<=1e9。
Solution
这其实就是要求第k个µ[i](莫比乌斯函数)不为0的数。
然而k太大数组开不下来是吧,于是这么处理。
二分答案x,问题转化为求[1,x]间有多少个没有完全平方因子的数。
容斥,加上全部,减去一个质数的平方的倍数个数,加上两个质数乘积的平方的倍数个数...
然后发现,每个数的系数就是µ
这也说明了莫比乌斯的原理就是容斥,µ函数就是容斥系数
具体来说,对于每一个i<=sqrt(x),对于ans的贡献就是µ[i]*int(n/(i*i))(向下取整)
有 于是二分上限2*k
复杂度为log(n)*sqrt(n)
Code
一开始直接mid=(l+r)>>1溢出T了一发
正确姿势mid=l>>1+r>>1+(l&r&1)
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int maxn=5e4+5; 7 8 int mu[maxn],flag[maxn]; 9 int prime[maxn],cnt; 10 11 int getmu(){ 12 mu[1]=1; 13 for(int i=2;i<maxn;i++){ 14 if(!flag[i]){ 15 prime[++cnt]=i; 16 mu[i]=-1; 17 } 18 for(int j=1;i*prime[j]<maxn&&j<=cnt;j++){ 19 flag[i*prime[j]]=1; 20 if(i%prime[j]==0){ 21 mu[i*prime[j]]=0; 22 break; 23 } 24 mu[i*prime[j]]=-mu[i]; 25 } 26 } 27 } 28 29 int work(int n){ 30 int ret=0; 31 for(int i=1;i*i<=n;i++) 32 ret+=mu[i]*int(1.0*n/(i*i)); 33 return ret; 34 } 35 36 int main(){ 37 int T,k; 38 scanf("%d",&T); 39 getmu(); 40 41 while(T--){ 42 scanf("%d",&k); 43 int l=1,r=2*k; 44 while(l<r){ 45 int mid=(l>>1)+(r>>1)+(l&r&1); 46 if(work(mid)>=k) r=mid; 47 else l=mid+1; 48 } 49 printf("%d\n",l); 50 } 51 return 0; 52 }