最新要闻
- 滁州市全力守好高考学子“舌尖安全”
- 电脑鼠标点击一次出现双击的效果是什么原因_鼠标单击出现双击效果
- 陕西煤业:5月自产煤销量1446.58万吨 同比增长9%
- 今头条!双胞胎拿错准考证!骁骑5分钟调换并暖心祝福:考好点哟
- AMD Zen5锐龙8000第一次露面:冲上6GHz!功耗不变-每日热讯
- 当前观察:PCIe 5.0全拉满!七彩虹CVN B650 GAMING FROZEN V14评测:同价位最好的大板
- 环球微资讯!市区不是油老虎了!坦克300 PHEV申报:电池超大
- 广汽董事长曾庆洪:想死的企业就早点降价吧
- 太仓房博会抛出多重礼包 点燃房市“夏日激情”
- 环球微动态丨凤凰点职业 凤凰令什么职业好
- 首次中国-巴基斯坦-伊朗三方司局级反恐安全磋商举行 外交部介绍情况
- 视频|忘带身份证补录证明 铁骑为其领路办理
- 广汽集团曾庆洪:汽车产业告别高增长黄金时代,淘汰赛加速进行 全球视讯
- 大爷将2台电动车焊一起自制代步车:觉得代步车太贵
- 小金毛冲进考场被无情请出 网友:忘带双证了?
- 突发!中国电信大面积崩溃:手机没信号、电话空号
手机
iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?
- 警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案
- 男子被关545天申国赔:获赔18万多 驳回精神抚慰金
- 3天内26名本土感染者,辽宁确诊人数已超安徽
- 广西柳州一男子因纠纷杀害三人后自首
- 洱海坠机4名机组人员被批准为烈士 数千干部群众悼念
家电
【数学】各种积性函数的线性筛法_微速讯
【数学】各种积性函数的线性筛法
前置芝士:几种特殊的积性函数的定义及基本性质。
定义
积性函数:若函数\(f(x)\)满足\(f(x) = 1\)且\(\forall x,y \in N^+,gcd(x,y) = 1\) ,都有\(f(xy) = f(x)f(y)\),则\(f(x)\)为积性函数。
(资料图片)
完全积性函数:若函数满足\(f(x) = 1\)且\(\forall x,y \in N^+\),都有\(f(xy) = f(x)f(y)\),则\(f(x)\)为积性函数。
判定
特殊例子:(以下都是积性函数)
\(\epsilon(n) = [n = 1]\) (\(n = 1\)时为1,否则为0)
\(id_k(n) = n^k\),当\(k = 1\)时简记为\(id(n)\)
\(1(n) = 1\)
\(\sigma_k(n) = \sum_{d|n}d^k\),当\(k = 0\)时为因数个数,记为\(d(n)\),\(k = 1\)时为因数和,记为\(\sigma(n)\)
\(\phi(n) = \sum_{i = 1}^n [gcd(i,n) = 1]\)
\[\mu(n) = \begin{cases}1 \ \ \ \ n = 1\\(-1)^k \ \ \ \ 所有质因数次数不超过1且有k种质因数\\0 \ \ \ \ otherwise\\\end{cases}\]对于函数之间运算产生的函数,有以下规律:
若\(f(x)\)和\(g(x)\)都是积性函数,则以下函数也是积性函数:
\[h(x) = f(x^p)\\h(x) = f^p(x)\\h(x) = f(x)g(x)\\f(x)和g(x)的Dirichlet卷积,即:h(x) = \sum_{d|x}f(x)g(\frac gd)\]有时在题目中,会要求筛出\(1 \to 10^6\)甚至\(1 \to 10^7\)的这些函数值,时间复杂度要求\(O(n)\),我们如何计算这些东西呢?
我们发现一个普遍的性质,这些函数当自变量取值为质数时,都可以简单地\(O(1)\)求出,于是我们将这个过程代入筛素数的线性筛,再尝试每次用质数(创造互质条件)和积性函数的性质求出函数值。
不会线性筛质数的自行前往:P3383 【模板】线性筛素数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
具体对于每一个函数将怎么做呢?
欧拉函数\(\phi\)
直接枚举比\(x\)小的数显然不可行,我们知道欧拉函数有一种计算方法:
\[\phi(x) = x\prod_{p \in prime\ \& \ p|x}\frac {p - 1}p\]因为无论一个质数\(p\)在\(x\)的分解中出现多少次,它\(\frac {p - 1}p\)的贡献都只有一次,结合到质数筛中我们每次都用一个质数去乘以一个其他数,可以分类讨论:
\[\phi(x) = x - 1\ \ \ if \ x \in prime\]以及(\(p\)是线性筛中每次枚举的质数)
\[\phi(x * p) = \begin{cases}\phi(x) * \phi(p)\ \ \ \ p \mid x\\\phi(x) * p\ \ \ \ p \nmid x\end{cases}\]因为\(p \mid x\)时,满足\(gcd(p,x) = 1\),所以可以直接相乘。
\(p \nmid x\)时,\(x\)中已有\(p\),贡献就只有乘上了\(p\)倍。
由于线性筛一定会把每个数筛一次,所以保证范围内的数全都计算了\(\phi\)值。
(代码中的\(\phi(p)\)写作了\(p - 1\),因为\(p\)是质数,两者是等价的,后面的函数也一样)
Code
inline void init(){ phi[1] = 1; for(R int i = 2;i <= N - 1;i++) { if(!vis[i]) { phi[i] = i - 1; prime[++tot] = i; } for(R int j = 1;j <= tot && i * prime[j] < N;j++) { vis[prime[j] * i] = 1; if(!(i % prime[j])) { phi[prime[j] * i] = (prime[j] - 1) * phi[i]; break; } phi[prime[j] * i] = phi[i] * prime[j]; } }}
莫比乌斯函数\(\mu\)
同\(\phi\)的分析方法,我们不难发现,当自变量是一个质数的时候,其一定只有一个质因数。
即
\[\mu(x) = -1\ \ \ if\ x \in prime\]考虑到线性筛中一个任意数和一个质数相乘的情况,如果\(p \mid i\),那么\(p * i\)一定含有超过一个\(p\),\(\mu\)为0,如果\(p \nmid i\),至少说明乘上\(p\)这一操作让\(i\)多了一个质因数,不管之前\(\mu\)是否为0,将\(\mu\)取反,一定满足其定义。
\[\mu(i * p) = \begin{cases}\mu(i) * \mu(p) = -\mu(i)\ \ \ \ p \nmid i\\0\ \ \ \ p \mid i\\\end{cases}\]Code
inline void init(){ miu[1] = 1; for(R int i = 2;i <= N - 1;i++) { if(!vis[i]) { miu[i] = -1; prime[++tot] = i; } for(R int j = 1;j <= tot && i * prime[j] < N;j++) { vis[prime[j] * i] = 1; if(!(i % prime[j])) { miu[prime[j] * i] = 0; break; } miu[prime[j] * i] = -miu[i]; } }}
因数和\(\sigma\)
精彩的部分来了,本人第一次看到时也十分震撼。
方法源自ldysy2102 - 博客园的博客线性筛约数个数、约数和的新方法 - ldysy2102 - 博客园 (cnblogs.com)
首先当\(p\)为质数时,因数只有\(1、p\)两个,因数和\(\sigma(p) = p + 1\)
由唯一分解定理,一个数可以被分解为:
\[x = \prod_{i = 1\ \& \ p_i \in prime}^kp_i^{c_i}\]这个数的因数就是这些质因数任意次数的任意组合,每个质因数都可以选择\(0 \to c_i\)个。所以
每个因数就是质因数的任意次方乘起来,是:
\[\sigma(x) = (1 + p_1 + p_1^2 + .. + p_1^{c_1})(1 + p_2 + p_2^2 + .. + p_2^{c_2})...(1 + p_k + .. + p_k^{c_k})\]令\((1 + p_2 + ..)..(1 + p_k + ..) = T\),再次讨论线性筛中一个质数乘上一个任意数的情况,在\(p \mid i\)时,我们钦定乘上的质因数是\(p_1\):
\[\sigma(x * p_1) = (1 + p_1 + .. + p_1^{c_1 + 1})T\\= \sigma(x) + p_1^{c_1 + 1}T\]\[\sigma(\frac x{p_1}) = (1 + p_1 + .. + p_1^{c_1 - 1})T\\= \sigma(x) - p_1^{c_1}T\]两个柿子只有\(T\)前的系数不一样,将\(②\)式乘上\(p_1\)再加上\(①\),神奇的事情发生了:
\[p_1\sigma(\frac x{p_1}) + \sigma(x * p_1) = (p_1 + 1)\sigma(x)\]\[\sigma(x * p_1) = (p_1 + 1)\sigma(x) - p_1\sigma(\frac x{p_1})\]这样,在知道\(p_1\)和\(x\)之后我们就可以在枚举质数时完成计算。
由于这些函数都是积性函数,所以当\(p \nmid x\)时的处理方法都是一样的。
Code
inline void init(){ sig[1] = 1; for(int i = 2;i < N;i++) { if(!vis[i]) { prime[++tot] = i; sig[i] = i + 1; } for(int j = 1;j <= tot && i * prime[j] < N;j+) { vis[i * prime[j]] = 1; if(!(i % prime[j])) { sig[i * prime[j]] = ((prime[j] + 1) * sig[i] % MOD - prime[j] * sig[i / prime[j]] % MOD + MOD) % MOD; break; } sig[i * prime[j]] = sig[i] * (prime[j] + 1); } }
因数个数d
同理,首先发现当\(p\)为质数时,因数个数\(d(p) = 2\)
对于\(x\),唯一分解后得到
\[d(x) = (c_1 + 1)(c_2 + 1)...(c_k + 1)\]\[d(x) = (c_1 + 1)T\]\[d(x * p_1) = (c_1 + 2)T\]\[d(\frac x{p_1}) = c_1T\]所以
\[d(x * p_1) + d(\frac x{p_1}) = 2d(x) \]所以最终得到:
\[d(x * p_1) = 2d(x) - d(\frac x{p_1})\]Code
inline void init(){ d[1] = 1; for(int i = 2;i < N;i++) { if(!vis[i]) { prime[++tot] = i; d[i] = 2; } for(int j = 1;j <= tot && i * prime[j] < N;j+) { vis[i * prime[j]] = 1; if(!(i % prime[j])) { d[i * prime[j]] = 2 * d[i] - d[i / prime[j]]; break; } d[i * prime[j]] = d[i] * 2; } }}
关键词:
【数学】各种积性函数的线性筛法_微速讯
滁州市全力守好高考学子“舌尖安全”
电脑鼠标点击一次出现双击的效果是什么原因_鼠标单击出现双击效果
陕西煤业:5月自产煤销量1446.58万吨 同比增长9%
今头条!双胞胎拿错准考证!骁骑5分钟调换并暖心祝福:考好点哟
AMD Zen5锐龙8000第一次露面:冲上6GHz!功耗不变-每日热讯
当前观察:PCIe 5.0全拉满!七彩虹CVN B650 GAMING FROZEN V14评测:同价位最好的大板
环球微资讯!市区不是油老虎了!坦克300 PHEV申报:电池超大
广汽董事长曾庆洪:想死的企业就早点降价吧
太仓房博会抛出多重礼包 点燃房市“夏日激情”
环球微动态丨凤凰点职业 凤凰令什么职业好
首次中国-巴基斯坦-伊朗三方司局级反恐安全磋商举行 外交部介绍情况
视频|忘带身份证补录证明 铁骑为其领路办理
微速讯:CAN通信(二) :协议介绍
详解驱动开发中内核PE结构VA与FOA转换|热资讯
全球视点!MegEngine 动态执行引擎-Imperative Runtime 概述
当前聚焦:【新华500】新华500指数(989001)8日低开高走涨0.66%
广汽集团曾庆洪:汽车产业告别高增长黄金时代,淘汰赛加速进行 全球视讯
大爷将2台电动车焊一起自制代步车:觉得代步车太贵
小金毛冲进考场被无情请出 网友:忘带双证了?
突发!中国电信大面积崩溃:手机没信号、电话空号
显卡带来巨额利润 英伟达股价还能再涨30% 五大看涨理由…… 播资讯
今日精选:看似灯泡其实是个智能家居摄像机!萤石C8b 4G版图赏
天天微头条丨头部 UP 主入局,B 站带货时代来了?
理论+示例,详解GaussDB(DWS)资源管理 环球最新
C++ 引用
跟着源码学IM(十一):一套基于Netty的分布式高可用IM详细设计与实现(有源码)|当前快讯
观天下!MySQL百万级数据大分页查询优化的实现
矩形图的奇妙世界:揭开数据背后的故事 热点聚焦
中意悦享安康重疾险怎么样?保什么? 每日热讯
全球金融周期:趋势和影响——人民银行副行长、外汇局局长潘功胜在第十四届陆家嘴论坛上的主题演讲
弥勒岩在福清什么地方_弥勒岩
商家被大学生“占便宜”到崩溃引热议 7天无理由退货该取消吗?勿以恶小而为之|每日焦点
浙大创造出新物质:兼具硬度和弹性 真五边形战士
佛山一考生第一天走错考场:第二天赶不上公交 两次获救助 环球百事通
高考生出考场接受采访 同学跑来喊话:加强李信 环球热文
MediaTek天玑开发者中心官网上线 天玑生态圈加速引领移动应用体验进化 世界报道
每日看点!notify party和consignee(外贸单据中CONSIGNEE和NOTIFY PARTY有什么区别)
海口一老人街边突然摔倒,两小伙上前将人扶起 焦点速看
steam好友聊天闪退_steam好友功能激活
浙江省养老金调整方案及计算公式表 2022~2023年浙江省养老金调整方案细则最新消息(全文)
李云泽:坚决消除监管的空白和盲区 环球观热点
天天动态:以为走错 到了新考场发现这下真错了:女生闹大乌龙 幸运没耽误考试
不接受没用!欧美要把全球热门IP都改为黑人 塞尔达公主是黑人 太过分了?
百事通!618又要来了,江苏省消保委发布消费提示
岳阳县疾病预防控制局揭牌成立 焦点消息
深度学习应用篇-计算机视觉-目标检测[4]:综述、边界框bounding box、锚框(Anchor box)、交并比、非极大值抑制NMS、SoftNMS
Openjob:更强大、更智能的新一代分布式任务调度框架|世界热推荐
特斯拉被曝动员中国供应商出海 去墨西哥复制“上海工厂”|每日报道
官方重要提醒!网易暴雪游戏退款申请即将截止
全球新资讯:一个游泳池里到底有多少尿?
世界热点评!一本书卖4.5万 日本研究员拆解比亚迪海豹视频流出:竟有些热血
全球微头条丨燃油绝唱! 第八代高尔夫终于改款:首次搭载大尺寸屏幕
天天热门:一字千年,方正字库的守正与创新
MySQL索引的数据结构 环球快资讯
焦点!原生AJAX案例浏览器报错:Cross origin requests are only supported for protocol
全球头条:springboot~jgroups实现节点间的通讯
轻松实现物联网通信的利器:MQTT网关神器——FluxMQ 当前视点
win10配置Electron安装环境以及解决报错-消息
当前热文:青春的答卷
世界最新:当事博主否认被强制执行:特斯拉还想让平台封杀我 不是谁都给你面子
奶凶!沃尔沃史上最小SUV EX30发布!纯电续航480km 3.6秒破百
天天通讯!端午节假期火车票今日开售:调休放三天假 高速不免费
世界新动态:弯道强才是真的强!问界M5智驾版重庆山路实测:尽享丝滑
焦点快报!140W满功耗RTX 4060助力!618百亿补贴ROG魔霸7 Plus到手价仅8999元
天天时讯:郑外名师评卷·高考数学:反刷题、反套路,重视基础,稳中求新
龙湾开展“红色星期天”活动 让“一老一小”共享红色温暖 环球焦点
世界微头条丨太卷了,史上最简单的监控系统 catpaw 简介
小车PID巡线调节 全球报资讯
易基因|一种全新的检测DNA羟甲基化的技术:ACE-Seq 环球时快讯
JPA单表存储List与模糊查询
医保缴费多少年才可以终身享受待遇?多少钱一年?
欧盟将强制禁用华为5G设备 热点在线
性价比口碑双冠王!魅族20 PRO成618四千档性能神机 天天热资讯
雾霾笼罩纽约 自由女神像被“吞没” :美国大片地区昏黄烟雾 宛如末日降临-世界热头条
世界头条:高考时没有一个孔子是饿着的:学子争相给先贤送吃的 期盼金榜题名
女子开门杀致骑手摔倒被罐车卷入车底:第一反应竟是观察车门|天天速递
Adata 展示其 1600W PSU 可以为四个 450W RTX 4090 供电
java~如何使用无符号整型 看热讯
文字效果 用背景渐变实现 波浪背景文字
P1585 魔法阵 题解
关注2023年河南高考丨免费午餐温暖高考学子
西安李姐茶叶蛋的家常做法?
有人在麦田插钢筋损坏收割机:钢筋还特意用麦子包裹 天天报道
帅不过3秒!RTX 4060游戏本挑战全景光追惨败 天天实时
黑龙江黑河村庄遭龙卷风袭击:多处房屋损毁|焦点关注
安卓阵营早已实现:iOS 17相机终于引入“水平”辅助线_天天报资讯
天天看点:买显卡“送”橘猫!COLORFIRE RTX 4060 Ti橘影橙8GB 评测:比公版强2%
当前时讯:文档在线预览(四)将word、txt、ppt、excel、图片转成pdf来实现在线预览
热讯:工会代表候选人初步人选推荐情况的报告_人选和候选人的区别是什么
组图|2023年海南陵水黎安国际教育创新试验区知识产权沙龙活动举行
多家饭店因在凉皮内放黄瓜丝被罚 网友吵翻:专家科普为大家好
第27次参加!高考钉子户梁实愁眉苦脸出考场 直言考得不好_世界今日报
天天实时:Epic祝福高考学子被指配图不佳 随后换成《原神》截图
天天信息:灵商的组成中包括(灵商)
吉视传媒:公司目前没有发展和推动有esim卡业务 今日精选
全球短讯!青海省邮政管理局联合相关部门调研“客货邮”融合发展情况
世界即时看!福达合金:截至本公告披露日 公司及其控股子公司担保余额为人民币约7.86亿元
职业发展战术设计:构建可持续积累的职业优势 每日关注
微控制器实时操作系统实践3任务信令和通信机制