筛 sigma_k
2024-10-20 16:19:00
问题
定义 \(\sigma_k(n)\) 表示 \(n\) 的所有约数的 \(k\) 次方和,即
\[\sigma_k(n)=\sum_{d\mid n}d^k
\]
\]
问题:求 \(\sigma_k(1),\sigma_k(2),\cdots,\sigma_k(n)\) .
线性筛
- 素数:直接 \(k\) 次方 .
- 没有的素因子:乘 \(k\) 次方 .
- 素因子:除掉再 \(k\) 次方 .
看不懂可以看 BZOJ2813 题解 .
杜教筛
令 \(\operatorname{Id}_k(n)=n^k\),则由定义:
\[\mu*1=\mathrm{Id}_k
\]
\]
\[\sigma_k=1*\mathrm{Id}_k
\]
\]
于是
\[\mu*\sigma_k=\mathrm{Id}_k
\]
\]
杜教筛即可 .
或者 Powerful Number 筛,但是我不会 .
复杂度不会算 .
最新文章
- python学习7
- C++_直接插入排序
- poj2406 KMP
- String.equals()方法的实现代码,
- Ambiguous mapping found. Cannot map 'xxxxController' bean method
- Data Structure导论的导论
- 修改MYSQL最大连接数的2种方法
- FFMPEG H264/H265 编码延迟问题
- PL\SQL学习笔记
- Android启动脚本init.rc(2)
- 四 Memcache
- CentOS7 搭建影梭服务器
- JS如何截取一段字符中,某一个字符的前面和后面的字符
- 垃圾wps弹出,现在连关闭按钮都不给了
- MySQL主从及主主环境部署
- UCML JS函数说明
- MySQL事物(一)事务隔离级别和事物并发冲突
- js代码实现购物车效果
- Centos 安装 GitLab 8.5.1 版本管理
- hi模板文件报乱码问题
热门文章
- 【HarmonyOS学习笔记】Slider组件实现图形可调旋转
- webpack与vite的对比
- 一文带你搞懂 Kafka 的系统架构(深度好文,值得收藏)
- 好客租房44-react组件基础综合案例-5发表评论-1
- SmartIDE v0.1.17 已经发布 - 模版库远程模式和插件市场公测
- java-去除html中的标签或者元素属性(正则表达式/jsoup)
- 【Python - pip source】工欲善其事,必先利其器 - 不要让 pip install timeout 成为你的烦恼
- vue项目经常遇到的Error: Loading chunk * failed
- c++ 树状数组
- .net core 抛异常对性能影响的求证之路