直接筛$\mu$?+爆算?再不行筛素数再筛个数?但不就是$\mu^2$的前缀和吗?
放。。。怕不是数论白学了$qwq$
思路:二分+容斥
提交:两次(康了题解)
题解:
首先答案满足二分性质(递增),然后就是如何快速$ck()$
首先观察到,$\lfloor \frac{n}{i^2} \rfloor$是$i^2$筛出来的完全平方数(和其倍数)的个数,但是显然这么筛会筛重一些数。
于是:容斥叭$qwq$
考虑如何配系数:所有数-被一个素因子的平方筛掉的+被两个素因子的平方筛掉的-被三个素因子的平方筛掉的+。。。
奇负偶正?
这不是$\mu$吗?
好的,筛出$\mu$,$sqrt(2*k)$(然鹅我也不知道为什么$2*k$是上界)的;然后二分答案。
$O(T*logn*\sqrt{n})$
#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
#define ull unsigned long long
#define ll long long
#define R register ll
#define pause (for(R i=1;i<=10000000000;++i))
#define In freopen("NOIPAK++.in","r",stdin)
#define Out freopen("out.out","w",stdout)
namespace Fread {
static char B[<<],*S=B,*D=B;
#ifndef JACK
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
#endif
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
if(ch==EOF) return EOF; do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return (ch<=||ch>=);}
inline void gs(char* s) {
register char ch; while(isempty(ch=getchar()));
do *s++=ch; while(!isempty(ch=getchar()));
}
} using Fread::g; using Fread::gs; namespace Luitaryi {
const int N=;
int mu[N],pri[N/],cnt,T,k;
bool vis[N];
inline void PRE() { mu[]=;
for(R i=;i<=N-;++i) {
if(!vis[i]) pri[++cnt]=i,mu[i]=-;
for(R j=;j<=cnt&&i*pri[j]<=N-;++j) {
vis[i*pri[j]]=true;
if(i%pri[j]==) break;
mu[i*pri[j]]=-mu[i];
}
}
}
inline bool ck(int x) { R ret=;
for(R i=,lim=sqrt(x);i<=lim;++i) ret+=mu[i]*(x/(i*i));
return ret>=k;
}
inline void main() { PRE();
T=g(); while(T--) {
k=g();
R l=,r=k<<;
while(l<r) {
R md=l+r>>;
if(ck(md)) r=md;
else l=md+;
} printf("%lld\n",l);
}
}
}
signed main() {
Luitaryi::main();
}
2019.07.17