Sumdiv(约数和问题)
题目地址
看到这题的题解,大佬都说是小学奥数,蔡得我不敢鸡声。
求 \(a^b\) 所有的约数之和 mod \(9901\) \((1<=a,b<=5*10^7)\)
题解
做这道题,我还赶紧去看了一下 唯一分解定理
我们先把 \(a\) 分解质因数
\[a=p_1^{c_1}*p_2^{c_2}*...*p_n^{c_n}\]
比如说 \(12\) 可以分成 \(2^2+3^1\) 啦
因为 同指数幂相乘,指数不变,底数相乘 ,所以就有:
\[a^b=p_1^{c_1*b}*p_2^{c_2*b}*...*p_n^{c_n*b}\]
根据 唯一分解定理,\(a^b\) 的约数和就是
\[(1+p_1+p_1^2+...+p_1^{c_1*b})*(1+p_2+p_2^2+...+p_2^{c_2*b})*...*(1+p_3+p_3^2+...+p_3^{c_3*b})\]
大佬看出了是等比数列,而我这个蒟蒻没有看出来
因为等比数列的求和公式要用除法,除法不满足 \(\text{mod}\) 的分配律
所以我们就迎来了这个题目的重点——分治
设 \(\text{sum}(p,c)\),为 \((1+p+p^2+...+p^{c})\)
- 若 \(c\) 为奇数,则有
\[\text{sum}(p,c)=(1+p+...+p^{\frac{c-1}{2}})+(p^{\frac{c+1}{2}}+...+p^c)\]
\[=1*(1+p+...+p^{\frac{c-1}{2}})+\frac{c+1}{2}*(1+p+...+p^{\frac{c-1}{2}})\]
\[=(1+\frac{c+1}{2})*\text{sum}(p,\frac{c-1}{2})\]
- 若 \(c\) 为偶数数,类似的有
\[\text{sum}(p,c)=(1+\frac{p}{2})*\text{sum}(p,\frac{p}{2}-1)*p^c\]
结合快速幂,时间复杂度上可以过得去
讲了这么多(虽然是看书),我忘了告诉你这个题目我是口胡的。
最新文章
- 3dmax导出到blend或者vs中
- Disk Space Usage 术语理解:unallocated, unused and reserved
- JAVA 求和程序
- Android之手机向导以及设置中心模块的开发
- Java解析采集模块
- Java冒泡排序,Java对象冒泡排序
- 利用pl/sql developer进行远程连接oracle server出现的问题及解决办法
- NeHe OpenGL教程 第二十四课:扩展
- 解决CSS中float:left后需要clear:both清空的繁琐步骤(转)
- Git的一些用法(建立新的branch)
- 整数运算:CPU内部只有加法运算
- Android-Launcher开发之ShortCut(1)
- 【问题解决方案】ImportError: No module named &#39;pygal&#39;
- JavaScript逗号操作符
- ARM的Jazelle技术【转】
- 伪静态与重定向--RewriteBase
- JavaScript之函数调用与被调用的上下文对象this
- rpc框架实现(持续更新)
- python------模块定义、导入、优化 ------->;Yaml, l模块
- FastAdmin 新年福袋进行中
热门文章
- elementUI下拉树组件封装
- R 时间戳转化
- Crypko 基于滚动条进行的动画是如何实现的?
- img下面出现了蜜汁空白
- 20160419&mdash;JS备忘:服务器回发刷新页面提示重试的解决方案。
- 阶段1 语言基础+高级_1-3-Java语言高级_06-File类与IO流_01 File类_3_绝对路径和相对路径
- ERROR 2002 (HY000): Can&#39;t connect to local MySQL server through socket &#39;/var/run/mysqld/mysqld.sock&#39;
- Nginx主要功能及使用
- Oracle 修改语言环境
- vue组件通信之父子组件通信