P4318 完全平方数
题目描述
求第 k 个,不是完全平方数也不是完全平方数倍数的数。
Solution
将数 x 分解质因子,设
x=p_1^{a_1}p_2^{a_2}\dots p_n^{a_n}
如果 x 不是完全平方数也不是完全平方数的倍数,那么必有 \forall a \leq 1
那么对于这样的数,有 \mu(x)^2=1
所以我们就要找到最小的 n 使得
\sum_{i=1}^n\mu^2(i) =k
但是这样很难做,我们考虑容斥
x=p_1p_2\dots p_n ,\forall p>1
如果 n 是奇数,那么它会给 \forall y,x^2|y 带来一个正贡献
如果 n 是偶数,那么它会给 \forall y,x^2|y 带来一个负贡献
那么这个正负刚好是 \mu(x)
所以我们就要求min(n)
\sum_{i=1}^n \mu(i)*\lfloor\frac{n}{i^2}\rfloor=k
#include<bits/stdc++.h>
#define ll long long
const int N = 1e5+10;
bool vis[N];
int prime[N];
int Mob[N];
int g[N],pre[N];
int k;
void Mobius_sieve(){
int cnt = 0;
vis[1] = 1;
Mob[1] = 1;
for(int i = 2; i < N; i++){
if(!vis[i])
prime[cnt++] = i, Mob[i] = - 1 , g[i] = 1;
for(int j = 0; j < cnt && 1LL * prime[j] * i < N; j++){
vis[prime[j] * i] = 1;
g[prime[j]*i] = g[i] + 1;
Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);
if(i % prime[j] == 0)
break;
}
}
for(int i=1;i<N;++i)
pre[i]=pre[i-1]+Mob[i];
}
int check(ll x){
ll ans = 0 ;
for(ll i=1;i*i<=x;++i)
ans += 1ll*Mob[i]*(x/(i*i));
return ans>=k;
}
int main(){
Mobius_sieve();
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&k);
ll l = 1e10 , r = 0;
while(l-1>r){
ll mid=l+r>>1;
if(check(mid))
l=mid;
else
r=mid;
}
printf("%lld\n",l);
}
}
0 条评论