BZOJ 2440

计算第 k 个不含平方因子的数。

显然。如果a含有平方因子。

则： μ(a)=0

如果不含有。则： μ(a)2=1

这跟莫比乌斯函数的定义有关。

我的一篇文章介绍过计算 ∑inμ(i)2 的方法。

http://blog.csdn.net/ZLH_HHHH/article/details/77969591

这种方法的复杂度是 O(n‾√) .所以直接二分答案即可。

下面是代码：

#include <algorithm> #include <string.h> #include <stdio.h> #include <cmath> #define MAXN 50000 using namespace std; typedef long long LL; int mu[MAXN]={0,-1}; int clar(int n) { LL tmp=0; int m=sqrt(n)+1; for(int i=1;i<m;i++) tmp+=(LL)mu[i]*(n/(i*i)); return (int)tmp; } int find__(LL L,LL R,int k) { while(L<=R) { LL mid=(L+R)>>1; int u=clar((int)mid); if(u>k) R=mid-1; else { if(u<k) L=mid+1; else R=mid-1; } } return (int)R+1; } int main() { for(int i=1;i<MAXN;i++) { mu[i]=-mu[i]; for(int j=i<<1;j<MAXN;j+=i) mu[j]+=mu[i]; } int T,n; scanf("%d",&T); while(T--) { scanf("%d",&n); printf("%d\n",find__(1,2000000000,n)); } return 0; }