设计师 网站/关键词排名优化流程

题目：

我是超链接

题解：

不能有完全平方数的因子。。有点眼熟，好像是$μ$函数？
因为合数可以表达为质数的乘积，我们只需要考虑质数的平方||质数*质数的平方
可以采用容斥原理：所有数字-1个质数的平方倍数+2个质数相乘的平方倍数-3个质数相乘的平方倍数…….
这个前面的符号似乎就是$μ$函数，对于某质因子幂的个数>=2，贡献直接就是0；然后k代表不同质因子的个数，$(-1)^k$仿佛正好就是容斥系数
你开始枚举一个数i，看看i的平方在[1,mid]中存在几个
我们可以知道如果输入K，答案不会超过2*K，我们采用二分，二分mid，每次check[1,mid]区间内有多少个不符合条件的数字

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define LL long long
using namespace std;
const int N=1e5;
int miu[N+5],tot,sc[N+5];bool ss[N+5];
void mu()
{miu[1]=1;for (int i=2;i<=N;i++){if (!ss[i]) sc[++tot]=i,miu[i]=-1;for (int j=1;j<=tot && sc[j]*i<=N;j++){ss[sc[j]*i]=1;if (i%sc[j]==0) {miu[i*sc[j]]=0;break;}else miu[i*sc[j]]=-miu[i];}}
}
LL check(LL mid)
{LL ans=0;int i;for (i=1;i<=sqrt(mid);i++)ans+=(LL)miu[i]*mid/(i*i);return ans;
}
int main()
{int T,k;mu();scanf("%d",&T);while (T--){scanf("%d",&k);LL l=1,r=k*2,ans;while (l<=r){LL mid=(l+r)>>1;if(check(mid)>=k) ans=mid,r=mid-1;else l=mid+1;}printf("%lld\n",ans);}
}