[bzoj2440]完全平方数[中山市选2011][莫比乌斯函数][线性筛][二分答案]
2024-08-30 23:06:22
题意:求第k个分解质因子后质因子次数均为一的数,即求第k个无平方因子数。
题解:
首先二分答案mid,那么现在就是要求出mid以内的无平方因子数的个数。
其次枚举$\sqrt{mid}$内的所有质数,由容斥原理
$Num=0个质数平方的倍数的数量(1的倍数)-1个质数平方的倍数的数量(9,25...的倍数)$
$+2个质数平方的倍数的数量(36,100...的倍数)...$
可以发现对于一个数x,x的倍数数量对答案的贡献符号为$\mu(x)$。
例如:9的倍数数量最答案的贡献是$\mu(9)\lfloor{\frac{mid}{9}}\rfloor=-\lfloor{\frac{mid}{9}}\rfloor$
所以最终mid以内的个数为
$Cnt=\sum\limits^{\lfloor{\sqrt{mid}}\rfloor}_{i=1}(\mu(i)\lfloor{\frac{mid}{i^2}}\rfloor)$
其中莫比乌斯函数为积性函数所以可以用线性筛预处理。
#include <bits/stdc++.h> using namespace std; int T,n,p[],Mu[],noprime[];
bool visited[]; void Mobius(const int N)
{
int pnum=; Mu[]=;
for(int i=;i<N;i++)
{
if(!visited[i]) { p[pnum++]=i; Mu[i]=-; }
for(int j=;j<pnum && i*p[j]<N;j++)
{
visited[i*p[j]]=true;
if(i%p[j]==) { Mu[i*p[j]]=; break; }
Mu[i*p[j]]=-Mu[i];
}
}
} int Check(const int x)
{
int temp=sqrt(x),Ans=;
for(int i=;i<=temp;++i)
Ans+=Mu[i]*(x/i/i);
return Ans;
} int main()
{
scanf("%d",&T); Mobius();
while(T--)
{
scanf("%d",&n);
int l=,r=2e9;
while(l<r-)
{
int mid=l+((r-l)>>);
if(Check(mid)>=n)r=mid;
else l=mid;
}
printf("%d\n",r);
}
return ;
}
最新文章
- iOS APP上架过程常见问题
- 单例模式(Java)
- 第三次作业——for 语句及分支结构else-if
- 给出一个长度为n的数列,请对于每一个数,输出他右边第一个比他大的数。n<;=100000.
- IIS没有ASP.NET选项卡
- @Autowired与@Resource用法
- lucene 实现word,pdf全文检索源码
- 利用智能手机(Android)追踪一块磁铁(二)
- linux系统调用之用户管理
- DBS:TestSys
- postgresql-10.1-3-windows-x64 安装之后,起动pgAdmin 4问题(win10)
- rsa加密解密, 非对称加密
- 设计模式之Proxy(代理)(转)
- 并发编程—— FutureTask 源码分析
- SD从零开始57-58,第三方订单处理,跨公司销售
- Ribbon Status Bar
- 特殊字符搜索网站 http://symbolhound.com/
- dedecms织梦 v5.6 两处跨站漏洞
- 使用SQL查询连续号码段
- am335x -- kio 控制接口