最近本人脑洞大开，发现了一种线性筛约数个数和约数和的一种神奇方法。
目前网上的方法基本都是利用$num[i]$数组记录$i$最小的质因子的个数，然后进行转移。
其实可以省去$num[i]$数组，直接进行递推。
设$n$的标准分解式为：
$$n=p_{1}^{r_{1}}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
那么$n$的约数个数及约数和分别为：
$$d(n)=prodlimits_{i=1}^{k}(r_{i}+1)$$
$$sigma(n)=prodlimits_{i=1}^{k}(1+p_{i}+p_{i}^{2}+cdots+p_{i}^{r_{i}})$$
要想线性筛一个积性函数$f(i)$，只需要知道4个东西。
$1:$$f(1)=?$
很显然，$d(1)=1$,$sigma(1)=1$;
$2:$$f(p)=?$，其中$p$为质数。
同样很显然，$d(p)=2$,$sigma(p)=p+1$;
$3$、$4:$$f(icdot p_{j}) = ?$，$i$与$p_{j}$互质或不互质。
先说线性筛约数个数的方法，
若$i$与$p_{j}$互质，则我们可以利用积性函数的性质直接推出：
$$d(icdot p_{j})=d(i)cdot d(p_{j})=2d(i)$$
最后思考当$i$与$p_{j}$不互质的时候，考虑$i$，$icdot p_{j}$，$frac{i}{p_{j}}$的关系(由线性筛过程可知,$i$与$p_{j}$不互质即$p_{j}|i$)
这里不妨设$p_{j}=p_{1},r_{j}=r_{1}$：
$$i=p_{1}^{r_{1}}p_{2}^{r_{2}}cdot cdots p_{k}^{r_{k}}$$
$$icdot p_{1}=p_{1}^{r_{1}+1}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
$$frac{i}{p_{1}}=p_{1}^{r_{1}-1}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
则有：
$$d(i)=(r_{1}+1)(r_{2}+1)cdots(r_{k}+1)$$
$$d(icdot p_{1})=(r_{1}+2)(r_{2}+1)cdots(r_{k}+1)$$
$$d(frac{i}{p_{1}})=r_{1}(r_{2}+1)cdots(r_{k}+1)$$
设$d(i)$中$r_{1}+1$后面的一大坨为$T$,即可表示为：
$$d(i)=(r_{1}+1)T$$
$$d(icdot p_{1})=(r_{1}+2)T=d(i)+T$$
$$d(frac{i}{p_{1}})=r_{1}T=d(i)-T$$
将$2$、$3$式相加，整理得
$$large{d(icdot p_{1})=2d(i)-d(frac{i}{p_{1}})}$$
补上线性筛约数个数的代码：
int pr[N],vis[N],d[N],cnt;
void make(int n)
{
d[1] = 1;
for(int i = 2;i<=n;i++)
{
if(!vis[i])pr[++cnt] = i,d[i] = 2;
for(int j = 1;i*pr[j]<=n&&j<=cnt;j++)
{
vis[i*pr[j]] = 1;
if(i%pr[j]==0)
{
d[i*pr[j]] = d[i]*2-d[i/pr[j]];
break;
}d[i*pr[j]] = d[i]*2;
}
}
}
相比于使用$num$数组，这段代码就显得更加简洁,更重要的是它节省了内存.
同样，约数和也可以像这样筛出来.
$i$与$p_{j}$互质时，
$$sigma(icdot p_{j})=sigma(i)cdot sigma(p_{j})=sigma(i)(p_{j}+1)$$
不互质时，同样考虑$sigma(i)$、$sigma(frac{i}{p_{1}})$同$sigma(icdot p_{1})$的关系.
设：
$$i=p_{1}^{r_{1}}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
$$icdot p_{1}=p_{1}^{r_{1}+1}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
$$frac{i}{p_{1}}=p_{1}^{r_{1}-1}p_{2}^{r_{2}}cdots p_{k}^{r_{k}}$$
则有：
$$sigma(i)=(1+p_{1}+cdots+p_{1}^{r_{1}})(1+p_{2}+cdots+p_{2}^{r_{2}})cdots(1+p_{k}+cdots+p_{k}^{r_{k}})$$
$$sigma(icdot p_{1})=(1+p_{1}+cdots+p_{1}^{r_{1}+1})(1+p_{2}+cdots+p_{2}^{r_{2}})cdots(1+p_{k}+cdots+p_{k}^{r_{k}})$$
$$sigma(frac{i}{p_{1}})=(1+p_{1}+cdots+p_{1}^{r_{1}-1})(1+p_{2}+cdots+p_{2}^{r_{2}})cdots(1+p_{k}+cdots+p_{k}^{r_{k}})$$
同理，设后面的那一大串为$T$.
$$sigma(i)=(1+p_{1}+cdots+p_{1}^{r_{1}})T$$
$$sigma(icdot p_{1})=(1+p_{1}+cdots+p_{1}^{r_{1}+1})T=sigma(i)+p_{1}^{r_{1}+1}T$$
$$sigma(frac{i}{p_{1}})=(1+p_{1}+cdots+p_{1}^{r_{1}-1})T=sigma(i)-p_{1}^{r_{1}}T$$
将$3$式乘上$p_{1}$再与$2$式相加,得到
$$sigma(icdot p_{1})+p_{1}sigma(frac{i}{p_{1}})=(p_{1}+1)sigma(i)$$
整理，即:
$$large{sigma(icdot p_{1})=(p_{1}+1)sigma(i)-p_{1}sigma(frac{i}{p_{1}})}$$
最后补上线性筛约数和的代码
int pr[N],vis[N],sigma[N],cnt;
void make(int n)
{
sigma[1] = 1;
for(int i = 2;i<=n;i++)
{
if(!vis[i])pr[++cnt] = i,sigma[i] = i+1;
for(int j = 1;i*pr[j]<=n&&j<=cnt;j++)
{
vis[i*pr[j]] = 1;
if(i%pr[j]==0)
{
sigma[i*pr[j]] = sigma[i]*(pr[j]+1)-pr[j]*sigma[i/pr[j]];
break;
}sigma[i*pr[j]] = sigma[i]*(pr[j]+1);
}
}
}
事实上它还可以再短一点(附上约数个数和约数和放在一起的版本)：
int n,pr[N],vis[N],d[N],sigma[N],cnt;
void make(int n)
{
d[1] = sigma[1] = 1;
for(int i = 2;i<=n;i++)
{
if(!vis[i])pr[++cnt] = i,d[i] = 2,sigma[i] = i+1;
for(int j = 1;i*pr[j]<=n&j<=cnt;j++)
{
vis[i*pr[j]] = 1;
d[i*pr[j]] = d[i]<<1;
sigma[i*pr[j]] = sigma[i]*(pr[j]+1);
if(i%pr[j]==0)
{
d[i*pr[j]]-=d[i/pr[j]];
sigma[i*pr[j]]-=pr[j]*sigma[i/pr[j]];
break;
}
}
}
}