正解: 容斥 / 杜教筛 + 二分
解题报告:
传送门 $QwQ$
首先一看这数据范围显然是考虑二分这个数然后 $check$ 就计算小于等于它的不是讨厌数的个数嘛.
于是考虑怎么算讨厌数的个数?
看到这个讨厌数说, 不能是完全平方数的倍数, 不难想到可以理解为将 $x$ 质因数分解后不存在指数大于 1 的情况.
这时候自然而然能联想到莫比乌斯函数? 因为根据定义有, 只有质数大于 1 时等于 0 其他时候为 $\pm 1$.
所以答案就 $\sum (\mu(i))^2$. 杜教筛就好 (因为, 我, 不会杜教筛, 所以一句话就带过去了 $kk$, 可能等我学了杜教筛会来补锅的趴,,?$QwQ$
法二考虑容斥, 即答案 = 总数 - 一个质因子的平方的倍数 + 两个不同质因子的平方的倍数 - 三个不同质因子的平方的倍数...
不解释了趴我 $jio$ 得还挺显然的 $QwQ$
考虑怎么求呢? 再次想到莫比乌斯函数的特殊性质, 考虑枚举这个平方根 $i$, 贡献显然就 $\frac{n}{i^2}$. 考虑系数? 发现系数取决于质因子的个数的奇偶性, 依然根据莫比乌斯函数的定义有, 质因子个数为奇数时为负一, 质因子个数为偶数是为正一. 且质因子质数大于 1 时等于 0 保证了一定是不同质因子.
综上, 可以得到答案 $ans=\sum_{i=1}^{i^2\leq n}\mu(i)\cdot \frac{n}{i^2}$
$over$?
- #include<bits/stdc++.h>
- using namespace std;
- #define il inline
- #define fi first
- #define sc second
- #define gc getchar()
- #define mp make_pair
- #define int long long
- #define P pair<int,int>
- #define ri register int
- #define rc register char
- #define rb register bool
- #define rp(i,x,y) for(ri i=x;i<=y;++i)
- #define my(i,x,y) for(ri i=x;i>=y;--i)
- #define e(i,x) for(ri i=head[x];i;i=edge[i].nxt)
- const int N=1e6+10;
- int n,m,miu[N],pr[N],pr_cnt;
- bool is_pr[N];
- il int read()
- {
- rc ch=gc;ri x=0;rb y=1;
- while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
- if(ch=='-')ch=gc,y=0;
- while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
- return y?x:-x;
- }
- il void pre()
- {
- miu[1]=1;
- rp(i,2,N-10)
- {
- if(!is_pr[i])pr[++pr_cnt]=i,miu[i]=-1;
- rp(j,1,pr_cnt)
- {
- if(i*pr[j]>N-10)break;;is_pr[i*pr[j]]=1;
- if(!(i%pr[j])){miu[i*pr[j]]=0;break;}
- miu[i*pr[j]]=-miu[i];
- }
- }
- }
- il int check(ri x)
- {
- ri ret=0;
- for(ri i=1;i*i<=x;++i)ret+=miu[i]*(x/i/i);
- return ret;
- }
- signed main()
- {
- //freopen("4318.in","r",stdin);freopen("4318.out","w",stdout);
- ri T=read();pre();
- while(T--)
- {ri K=read(),l=1,r=K<<1;while(l<r){ri mid=(l+r)>>1;if(check(mid)>=K)r=mid;else l=mid+1;}printf("%lld\n",l);}
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3216558.html