标签:莫比乌斯函数,容斥
完全平方数
题目描述
小 X 自幼就很喜欢数。但奇怪的是，他十分讨厌完全平方数。他觉得这些数看起来很令人难受。由此，他也讨厌所有是完全平方数的正整数倍的数。然而这丝毫不影响他对其他数的热爱。
这天是小X的生日，小 W 想送一个数给他作为生日礼物。当然他不能送一个小X讨厌的数。他列出了所有小X不讨厌的数，然后选取了第 K个数送给了小X。小X很开心地收下了。
然而现在小 W 却记不起送给小X的是哪个数了。你能帮他一下吗？
\(k \leqslant 10^9\)
思路点拨
k是比较大的,所以我们可以二分转check.怎么查询一个数 \(x\) 是第几个数,就是查询在 \(1\) 到 \(x\) 之间有多少个数没有平方因子.但是这样欧拉筛会爆掉,完全无法通过.而直接计算
\[\sum_{i=1}^{\sqrt x} \lfloor \dfrac{x}{i^2}\rfloor
\]
这样答案会偏大,因为举个例子,\(2^2\) 时, \(36\) 被统计了一次, \(3^2\) 时,它又被统计了一次.所以我们需要容斥一下,而这个容斥系数显而易见的就是莫比乌斯函数 \(\mu(i)\) .
这里解释一下为什么是莫比乌斯函数?
-
如果一个数的质因子有大于 \(1\) 的完全平方因子,这肯定会被算重.不考虑,此时莫比乌斯函数值刚好是 $0 $ .
-
一个数的质因子数量如果是奇数,那么它要么被算多了,要么没被算到
-
一个数的质因子数量如果是偶数,这肯定会被算重.
莫比乌斯函数的容斥天赋很高的好不好.
所以答案就是 \(\sum_{i=1}^{\sqrt x} \mu(i) \lfloor \dfrac{n}{i^2}\rfloor\) .
时空复杂度分析:时间 \(O(T \sqrt k \log k)\) , 空间 \(O(\sqrt k)\) , 要筛莫比乌斯函数.
\(code\)
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=1e5+10,N=1e5;
int n,T,miu[MAXN];
bool vis[MAXN];
void prepare(){
for(int i=1;i<=N;i++) miu[i]=1;
for(int i=2;i<=N;i++){
if(vis[i]) continue;
miu[i]=-1;
for(int j=i*2;j<=N;j+=i){
if(j%(i*i)==0)
miu[j]=0;
else miu[j]*=miu[i];
vis[j]=1;
}
}
}
int f(int x){
int cnt=0;
for(int i=1;i*i<=x;i++)
cnt+=miu[i]*(x/(i*i));
return cnt;
}
int solve(int x){
int l=1,r=1e10;
while(l<r){
int mid=(l+r)/2;
if(f(mid)>=x) r=mid;
else l=mid+1;
}
return l;
}
signed main(){
prepare();
T=read();
while(T--){
n=read();
printf("%lld\n",solve(n));
}
return 0;
}