2015/06/27

[BZOJ 2440] 完全平方数【莫比乌斯函数/容斥原理/二分法】

[Description] 求第k个无平方因子数。无平方因子数指分解之后所有质因数的次数都为1的数。
[Solution] 
我们可以进行二分操作,查找区间[1,x]里有几个无平方因子数,逐渐缩小范围依次求解。 
然而怎么计算区间[1,x]内无平方因子数的个数Q呢? 

根据容斥原理, 
Q=x-x内有一个平方因子的数+x内有两个平方因子的数-x内有三个平方因子的数… 
=x-x内(4的倍数个数+9的倍数的个数+25的倍数的个数)+x内(36(2*3*2*3)的倍数+100(2*5*2*5)的倍数)… 
=   这里写图片描述

我们发现,对于有奇数个质数平方的因子数取正,有偶数个质数平方的因子数取正,仔细一看,这不正是i的莫比乌斯函数值吗?于是可求出Q= 这里写图片描述
现在的问题是,对于某个n/(i*i),到底是取正还是取负呢? 
然后就可以愉快的AC辣!

[Code]
#include<cmath> #include<cstdio> typedef long long ll; const ll maxx=(ll)1<<32; const int maxlim=1<<16; bool form[maxlim]; int mu[maxlim]={0,1},prime[maxlim],cnt; void MakeMuList(){ //线性筛 for(int i=2;i<maxlim;i++){ if(!form[i]) prime[cnt++]=i,mu[i]=-1; for(int j=0,t=prime[j]*i;t<maxlim;j++,t=prime[j]*i){ form[t]=true; if(!(i%prime[j])){ mu[t]=0; break; } mu[t]=-mu[i]; } } } ll query(ll x){ int lim=sqrt(x); ll ans=x; for(int i=2;i<=lim;i++) ans+=mu[i]*(x/(i*i)); return ans; } void find(int k){ if(k==1){ printf("1\n"); return; } int num=0; ll l=1,r=1644934081,x=0; //r为二分上界 while(l<=r){ ll mid=(l+r)>>1; num=query(mid); if(num>=k) r=mid-1,x=mid; else l=mid+1; } printf("%lld\n",x); } int main(){ MakeMuList(); int kase; scanf("%d",&kase); while(kase--){ int k; scanf("%d",&k); find(k); } return 0; }