[SDOI2015]约数个数和
https://www.luogu.com.cn/problem/P3327
\(d(x)\)为\(x\)的约数个数,有\(T\)组询问,每次询问
\[\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij) \]的值.
\(1\leq T,n,m \leq 50000\).
\[\begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}d(ij)\\ &=\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}[\gcd(x,y)=1]\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\\ &=\sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{d|x\ and\ d|y}\mu(d)\lfloor\frac{n}{x}\rfloor\lfloor\frac{m}{y}\rfloor\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor\lfloor\frac{m}{yd}\rfloor\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor \sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{yd}\rfloor\\ \end{aligned} \]令
\[f(n)=\sum_{x=1}^{n}\lfloor\frac{n}{x}\rfloor \]则
\[f(n)=\sum_{i=1}^{n}d(i) \]除数函数\(d(n)\)是积性函数,可以\(\Theta(n)\)得到所有\(d(i)\),再处理一下前缀和就可以\(\Theta(1)\)计算\(f(n)\).
所以
\[\begin{aligned} &\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{xd}\rfloor \sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\frac{m}{yd}\rfloor\\ &=\sum_{d=1}^{\min(n,m)}\mu(d)f(\lfloor\frac{n}{d}\rfloor)f(\lfloor\frac{m}{d}\rfloor) \end{aligned} \]时间复杂度\(\Theta(T\sqrt{ \min(n,m)})\).
标签：约数,lfloor,frac,min,sum,个数,rfloor,mu,SDOI2015 From： https://www.cnblogs.com/yanchengzhi/p/17002035.html