BZOJ 2440 [中山市选2011]完全平方数 ——莫比乌斯函数
2024-08-30 20:04:36
$\sum_{i=1}^n[i==d^2*p]$ 其中p无平方因子
$=\sum_{d^2\mid n,d>=2}\sum_{i=1}^{\lfloor {n/d^2} \rfloor} \left| \mu(i) \right |$
然后就成了计算$\left| \mu(i) \right |$ 的前缀和?
但是貌似不太可能啊 然后我们重新考虑容斥。
发现最终的结果 s=一个质数平方的倍数-两个质数乘积平方的倍数-三个的-五个的+6个的
发现系数和$\mu$一样,然后就可以枚举d进行计算了
$$\sum_{d^2<=n}\mu(d)*\lfloor {n/d^2} \rfloor$$
貌似就可以了
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (ll i=j;i<=k;++i)
#define D(i,j,k) for (ll i=j;i>=k;--i)
#define ll long long
#define maxn 100005
int vis[maxn],mu[maxn],pr[maxn],top=0;
void init()
{
mu[1]=1;
F(i,2,maxn-1)
{
if (!vis[i]) vis[i]=1,pr[++top]=i,mu[i]=-1;
F(j,1,top)
{
if (i*pr[j]>=maxn) break;
vis[i*pr[j]]=1;
if (i%pr[j]==0){mu[i*pr[j]]=0;break;}
mu[i*pr[j]]=-mu[i];
}
}
} int t;ll k; ll test(ll n)
{
ll t=sqrt(n),ret=0;
F(i,1,t) ret+=mu[i]*(n/(i*i));
return ret;
} int main()
{
init();
scanf("%d",&t);
while (t--)
{
scanf("%lld",&k);
ll l=0,r=30000000000LL;
while (l<r)
{
ll mid=(l+r)>>1;
if (test(mid)>=k) r=mid;
else l=mid+1;
}
printf("%lld\n",r);
}
}
最新文章
- px,em,rem
- strcpy函数实现
- Shell编程检测监控mysql的CPU占用率
- 在VS中使用类模板出现出现LNK2019: 无法解析的外部符号错误。
- uva11059
- WinForm控件使用文章收藏整理完成
- poj 2987 最大闭合子图
- 拿到阿里,网易游戏,腾讯,smartx的offer的过程 (转)
- Mono for Andriod学习与实践(1)— 初体验
- 动画云创始人胥克谦&;amp;课程格子创始人李天放分享创业经历
- linux下配置ip地址四种方法(图文)
- 解决flask的端口占用
- ubantu和虚拟机tools 安装 小问题集结
- 微信小程序之:wepy框架
- 用CMD打开chrome并导航到百度(golang)
- 关于h5绘制canvas生成图片的注意点!
- Codeforces 629D Babaei and Birthday Cakes DP+线段树
- Appium+java 模拟键盘输入
- Python读取本地文档内容并发送邮件
- GatewayWorker 分布初试
热门文章
- UITabBarController、导航控制器、控制器关系
- FusionCharts 3.2.1 常用用法
- 最新深度ghost win7系统下载
- Clown without borders 2017/1/10
- Gym 100342F 	Move to Front (树状数组动态维护和查询)
- Python-OpenCV:cv2.imread(),cv2.imshow(),cv2.imwrite()
- 还有这种书,程序开发心理学(豆瓣) - 豆瓣读书,转载自:https://book.douban.com/subject/1141154/
- Bootstrap教程简介
- CS193p Lecture 9 - Animation, Autolayout
- Codeforces Round #510 #B