莫比乌斯反演习题：bzoj 2154 crash的数字表格

给定$n,m$，求$sum_{i=1}^{n}sum_{j=1}^{m}text{lcm}(i,j)$

$n,m le 10^7$

$$
begin{aligned}
n le m \
sum_{i=1}^{n}sum_{j=1}^{m}text{lcm}(i,j)
&=sum_{i=1}^{n}sum_{j=1}^{m}frac{ij}{(i,j)} \
&=sum_{d=1}^{n}frac{d^2}{d}sum_{i=1}^{lfloor frac{n}{d} rfloor}sum_{j=1}^{lfloor frac{m}{d} rfloor}ij[(i,j)=1] \
&=sum_{d=1}^{n}dsum_{i=1}^{lfloor frac{n}{d} rfloor}sum_{j=1}^{lfloor frac{m}{d} rfloor}ij[(i,j)=1] \
&=sum_{d=1}^{n}dsum_{i=1}^{lfloor frac{n}{d} rfloor}sum_{j=1}^{lfloor frac{m}{d} rfloor}ijsum_{d’ mid (i,j)}mu(d’) \
&=sum_{d=1}^{n}dsum_{d’=1}^{lfloor frac{n}{d} rfloor}mu(d’)sum_{i=1 wedge d’ mid i}^{lfloor frac{n}{d} rfloor}sum_{j=1 wedge d’ mid j}^{lfloor frac{m}{d} rfloor}ij \
&=sum_{d=1}^{n}dsum_{d’=1}^{lfloor frac{n}{d} rfloor}mu(d’)sum_{i=1}^{lfloor frac{n}{dd’} rfloor}id’sum_{j=1}^{lfloor frac{m}{dd’} rfloor}jd’ \
&=sum_{d=1}^{n}dsum_{d’=1}^{lfloor frac{n}{d} rfloor}mu(d’)(d’)^2 frac{(1+lfloor frac{n}{dd’} rfloor)lfloor frac{n}{dd’} rfloor}{2} frac{(1+lfloor frac{m}{dd’} rfloor)lfloor frac{m}{dd’} rfloor}{2} \
&=sum_{T=1}^{n}frac{(1+lfloor frac{n}{T} rfloor)lfloor frac{n}{T} rfloor}{2}frac{(1+lfloor frac{m}{T} rfloor)lfloor frac{m}{T} rfloor}{2} sum_{d mid T}frac{T}{d}mu(d)d^2\
&=sum_{T=1}^{n}frac{(1+lfloor frac{n}{T} rfloor)lfloor frac{n}{T} rfloor}{2}frac{(1+lfloor frac{m}{T} rfloor)lfloor frac{m}{T} rfloor}{2} Tsum_{d mid T}mu(d)d\
&=sum_{T=1}^{n}frac{(1+lfloor frac{n}{T} rfloor)lfloor frac{n}{T} rfloor}{2}frac{(1+lfloor frac{m}{T} rfloor)lfloor frac{m}{T} rfloor}{2} Tf(T) \
&=sum_{T=1}^{n}frac{(1+lfloor frac{n}{T} rfloor)lfloor frac{n}{T} rfloor}{2}frac{(1+lfloor frac{m}{T} rfloor)lfloor frac{m}{T} rfloor}{2} g(T) \
end{aligned}
$$

之后考虑$g(T)=Tf(T)$怎么求，即求$f(T)=sum_{d mid T}mu(d)d$

考虑线性筛，假设当前枚举到了$i$，且枚举到了素数$p_j$

若$i$是素数，则$f(i)=sum_{d mid i}mu(i)i=mu(1)1+mu(i)i=1-i$

若$p_j mid i$，则$f(ip_j)=sum_{d mid ip_j}mu(d)d=sum_{dtext{中没有}p_j}mu(d)d+sum_{dtext{中有}p_J}mu(d)d=f(i)$

若$p_jnot mid i$，则

$$
begin{align}
f(ip_j)
&=sum_{d mid ip_j}mu(d)d \
&=sum_{dtext{中没有}p_j}mu(d)d+sum_{dtext{中有}p_J}mu(d)d \
&=f(i)+sum_{ap_j mid ip_j}mu(ap_j)ap_j \
&=(1-p_j)f(i)
end{align}
$$