https://www.luogu.org/problem/P4318
分析
可以转化为二分 m 求 [1,m] 中有多少个无平方因子数
显然可以容斥: 0 个质数的平方个数 - 1 个质数的平方个数 + 2 个的......
容易发现容斥系数是莫比乌斯函数
线性筛预处理再二分即可
注意二分 l,r,mid 可能超出 longlong 范围
最终公式:
$ans=\sum _{i=1}^{\left \lfloor \sqrt{n} \right \rfloor} \mu (i)\left \lfloor \frac{n}{i^2} \right \rfloor$
- #include <iostream>
- #include <cstdio>
- #include <cmath>
- using namespace std;
- typedef long long ll;
- const int Inf=2147483647;
- const int N=46341;
- int T,k;
- int prime[N],miu[N],cnt;
- bool nonprime[N];
- void Prime() {
- miu[1]=1;
- for (int i=2;i<N;i++) {
- if (!nonprime[i]) prime[++cnt]=i,miu[i]=-1;
- for (int j=1;j<=cnt;j++) {
- if (i*prime[j]>=N) break;
- nonprime[i*prime[j]]=1;
- if (i%prime[j]==0) {
- miu[i*prime[j]]=0;
- break;
- }
- miu[i*prime[j]]=-1*miu[i];
- }
- }
- }
- bool Check(ll mid) {
- ll n=sqrt(mid),ans=0;
- for (int i=1;i<=n;i++) ans+=1ll*miu[i]*(mid/(i*i));
- return ans>=k;
- }
- int main() {
- Prime();
- for (scanf("%d",&T);T;T--) {
- scanf("%d",&k);
- ll l=1,r=Inf,mid,ans;
- while (l<=r) {
- mid=1ll*(l+r)>>1;
- if (Check(mid)) ans=mid,r=mid-1;
- else l=mid+1;
- }
- printf("%lld\n",ans);
- }
- }
- View Code
[莫比乌斯函数][容斥]BZOJ 2440 完全平方数
来源: http://www.bubuko.com/infodetail-3158917.html