数论|JZOJ5340. 【NOIP2017模拟9.2A组】春思(2017.9A组)
【数论|JZOJ5340. 【NOIP2017模拟9.2A组】春思(2017.9A组)】https://jzoj.net/senior/#main/show/5340
想法：
a=(p[1]^q[1])(p[2]^q[2])(p[i]^q[i)…( (p[i]为a的质因子，q[i]为对应的指数)
那么a的约数和=（1+p[1]+p[1]^2+….+p[1]^q[1]）*(1+p[i]+p[i]^2+…+p[i]^q[i])……
a^b实际上是对每个a的质因子的指数*b
a^b的约数和=（1+p[1]+p[1]^2+….+p[1]^(q[1]*b)）(1+p[i]+p[i]^2+…+p[i]^(q[i]*b))……
然后就是求出每个等比数列的和，在乘起来
用线筛求素数，a的质因子及其指数
然后对于每个等比数列
令S=1+p+p^2+p^3+….+p^q
pS=p+p^2+…..+p^(q+1)
pS-S=p^(q+1)-1
(pS-S)/(p-1)=S=(p^(q+1)-1)/(p-1)
所以求出(p^(q+1)-1)/(p-1)（逆元）就好啦
递归
对于每个等比数列
S=1+p+p^2+p^3+….+p^q
如果p%2==0
那么S=(1+p+p^2+p^(q/2))*(1+p^(q/2))
如果p%2==1
那么S=(1+p+p^2+p^(q/2(下取整)))*(1+p^(q/2)）+p^q
递归求解即可
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长