约数问题

约数个数

先看约数的个数：$d(n)$。

设$n=p_1^{a_1}p_2^{a_2}\dots{p_t^{a_t}},m|n,m=p_1^{b_1}p_2^{b_2}\dots{p_t^{b_t}}$。

$m$是$n$的一个约数，每个质因子上方的指数取值为$[0,a_1]$，也就是有$a_1+1$种可能，每一个质因子的改变都会产生一个新的约数，所以乘起来就是$d(n)=(a_1+1)\cdot(a_2+1)\cdot(a_3+1)\dots(a_t+1)$。

暴力求约数和

再来看简单的情况：求$\sigma_1(n)$，即求$m$每个约数的一次方的和。

for(int i=1;i<=n;i++)
	for(int j=i;j<=n;j+=i)//枚举i的倍数
		s[i]+=j;

枚举$i$的倍数$j$，因此$i$是$j$的因数，这样就可以 nlogn 的复杂度求出约数和，下面讲$O(n)$递推。

线性递推

求$\sigma_k(m)$:

代表$m$的每个约数的$k$次方的和。

枚举的话我们可以设$m=p_1^{a_1}p_2^{a_2}p_3^{a_3}\dots{p_t^{k_t}}$（指数大于0）。

那么：

$\sigma_k(m)=[(p_1^0)^k+(p_1^1)^k+(p_1^2)^k+\dots+(p_1^{a_1})^k]\cdot[(p_2^0)^k+(p_2^1)^k+(p_2^2)^k+\dots+(p_2^{a_2})^k]\cdot[(p_3^0)^k+(p_3^1)^k+(p_3^2)^k+\dots+(p_3^{a_3})^k]\dots[(p_t^0)^k+(p_t^1)^k+(p_t^2)^k+\dots+(p_t^{a_t})^k]$

也就是$\sigma_k(m)$的定义式，求解这个式子的复杂度是调和级数，约为 nlogn。

这个式子的解释就是对于$p_1$从$0\sim{a_1}$中任选一个指数，对于$p_2$从$0\sim{a_2}$中任选一个指数，……，一直到$p_t$，这样乘起来，这个数一定是$m$的约数。

我们对每一个$p$枚举这个指数，实际上就是枚举了所有的$m$的约数的$k$次方并把它们求和，这就是这个多项式的意义（不能理解请手动展开）。

我们线性筛的时候，枚举了一个$i$，使得$m=i\times{p}$，其中$p$是$m$的最小质因子。

我们也把$i$质因数分解一下：$i=p_1^{a_1}p_2^{a_2}p_3^{a_3}\cdots{p_t^{a_{t}}}$（注意此处的$i$的各个质因子与$m$的不是同一套）。

然后设$mm_i=p_1^{a_1}$，代表$i$质因数分解后的所有最小质因子的乘积，$mn_i=p_1$，代表$i$质因数分解后的最小质因子。

开始分类讨论：

1. $mn_i!=p$

首先$mn_i\ge{p}$，这是因为$p$是$m$的最小质因子，$mn_i$如果比它还小，那么$i$的最小的质因子也就会被换为$p$，总之$p$是最小的，不可能有其它因子比它还小。

$mn_i!=p$其实就是$mn_i>p$，而$mn_m=p$，因此$a_1=1$，即这项的指数为$1$。

那么$\sigma_k(p)=[(p_1^0)^k+(p_1^1)^k+(p_1^2)^k+\dots+(p_1^{a_1})^k]$，为前半部分；$\sigma_k(i)=[(p_2^0)^k+(p_2^1)^k+(p_2^2)^k+\dots+(p_2^{a_2})^k]\cdot[(p_3^0)^k+(p_3^1)^k+(p_3^2)^k+\dots+(p_3^{a_3})^k]\dots[(p_t^0)^k+(p_t^1)^k+(p_t^2)^k+\dots+(p_t^{a_t})^k]$，为后半部分，两者相乘，即$\sigma_k(m)=\sigma_k(p)\cdot{\sigma_k(i)}$。

2. $mn_i=p$
   1. $mm_i=i$

$i$质因数分解后所有的质因子都是一样的，都是$mn_i$，也就是$mm_i=(mn_i)^{a_1}$，设$mm_i=p^z=i$，即$a_1=z$。

而$mn_i=p$，因此$m=i\times{p}=p^{z+1}$，也就是说$m$的质因子现在只有$p$。

那么根据$\sigma_m(k)$的定义式，$\sigma_k(m)=(p^0)^k+(p^1)^k+(p^2)^k+(p^3)^k+\cdots+(p^{z+1})^k$（因为此时$a_1=z+1$，所以指数从$0$枚举到$z+1$）。

而$\sigma_k(i)=(p^0)^k+(p^1)^k+(p^2)^k+(p^3)^k+\cdots+(p^{z})^k$

那么就可以得到$\sigma_k(m)=\sigma_k(i)+(p^{z+1})^k=\sigma_k(i)+m^k$。

2. $mn_i=p$
   2. $mm_i!=i$

$i$质因数分解后除了$p$之外还有其它质因子。

$m=i\times{p}=p_1^{a_1}p_2^{a_2}p_3^{a_3}p_4^{a_4}\dots{p_t^{a_t}}$。

移一下项：

$i=p_1^{a_1-1}p_2^{a_2}p_3{a_3}p_4{a_4}\dots{p_t^{a_t}}$

所以$mm_i=p_1^{a_1-1}$，得到了$p_1^{a_1}=mm_i\times{p}$。

而后面那半部分$p_2^{a_2}p_3{a_3}p_4{a_4}\dots{p_t^{a_t}}=\dfrac{i}{mm_i}$

然后就像最开始那种情况一样了：

$\sigma_k(m)=\sigma_k(mm_i\times{p})\cdot{\sigma_k(\frac{i}{mm_i})}$。