直接筛 $\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[1<<15],*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=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
- if(ch==EOF) return EOF; do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
- } inline bool isempty(const char& ch) {return (ch<=36||ch>=127);}
- 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=32000;
- int mu[N],pri[N/6],cnt,T,k;
- bool vis[N];
- inline void PRE() { mu[1]=1;
- for(R i=2;i<=N-10;++i) {
- if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
- for(R j=1;j<=cnt&&i*pri[j]<=N-10;++j) {
- vis[i*pri[j]]=true;
- if(i%pri[j]==0) break;
- mu[i*pri[j]]=-mu[i];
- }
- }
- }
- inline bool ck(int x) { R ret=0;
- for(R i=1,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=1,r=k<<1;
- while(l<r) {
- R md=l+r>>1;
- if(ck(md)) r=md;
- else l=md+1;
- } printf("%lld\n",l);
- }
- }
- }
- signed main() {
- Luitaryi::main();
- }
- 2019.07.17
BZOJ 2440 [中山市选 2011]完全平方数 二分 + 容斥
来源: http://www.bubuko.com/infodetail-3126619.html