[学习笔记] 约数函数

众所周知,(d)(sigma)都是积性函数,今天我们来对这俩动刀子。

我打算只讲稍难(sigma),剩下的那个(d),留给大家自己思考。

根据定义得到:

(egin{aligned}sigma(p^k)=1+p+p^2+...+p^kend{aligned})

然后我们就能推导出(sigma)的求值式:

(egin{aligned}n=prod_{i=1}p_i^{c_i}end{aligned},)

(egin{aligned}sigma(n)=prod_{i=1}1+p_i+p_i^2...+p_i^{c_i}end{aligned})

尝试用线性筛构造这个函数:

(x=i imes p_1),其中(p)(x)的最小质因子,(egin{aligned}x=prod_{i=1}p_i^{c_i}end{aligned})

  • (x)为质数:(sigma(x)=1+x)

  • (i)(p_1)互质时:(sigma(x)=sigma(i) imessigma(p_1))

  • (i\%p_1=0)时:

    我们具体来讨论一下这个情况。

    (egin{aligned}sigma(x)=prod_{i=1}1+p_i+p_i^2+...+p_i^{c_i}end{aligned})

    (egin{aligned}sigma(i)=(1+p_1+p_2^2+..+p_1^{c_1-1})prod_{i=2}1+p_i+p_i^2+...+p_i^{c_i-1}end{aligned})

    我们想要直接通过(sigma(i))来求(sigma(x))显然是不现实的,因为我们不知道(c_1)是多少。

    那么我们应该怎么做呢?

    我们尝试把这个包含绝对关系的式子转换成包含相对关系的式子。

    因为我们(x)(i),从第二项开始就是一样的了,所以我们可以设:(egin{aligned}T=prod_{i=2}1+p_i+p_i^2+p_i^{c_i}end{aligned})

    然后式子就转换为了:

    (egin{aligned}sigma(x)=sigma(i)+p_1^{c_1} imes Tend{aligned})

    我们来考虑一下怎么把这个讨厌的(p_1^{c_1})给处理了。

    注意我们一开始的目标:把绝对关系转化成相对关系。

    既然我们不知道(p_1^{c_1} imes T)的值,那么我们能不能求出(p_1^{c_1-1} imes T)的值呢?

    注意到(egin{aligned}sigma(i)=sigma(frac i {p_1})+p_1^{c_1-1} imes Tend{aligned})

    然后怎么做应该就不用我多说了吧——盘他!

    (egin{aligned}sigma(x)&=sigma(i)+p imes(sigma(i)-sigma(frac i {p_1}))\&=(1+p) imessigma(i)-p imessigma(frac i{p_1})end{aligned})

然后我们就能直接用线性筛来求约数函数了。


最后,我在稍微写一下(d)的式子吧:

(egin{aligned}d(x)=2 imes d(i)-d(frac i {p_1})end{aligned})

原文地址:https://www.cnblogs.com/WR-Eternity/p/11023518.html