SDOI2015 约数个数和

问题描述

设d(x)为x的约数个数，给定N、M，求的值。

输入格式

输入文件包含多组测试数据。
第一行，一个整数T，表示测试数据的组数。
接下来的T行，每行两个整数N、M。

输出格式

T行，每行一个整数，表示你所求的答案。

样例输入

2
7 4
5 6

样例输出

110
121

数据规模

1<=N, M<=50000 1<=T<=50000

首先有一个结论：$d(ij)=\sum_{x|i}\sum_{y|j}[(x,y)=1]$，证明：https://www.cnblogs.com/GXZlegend/p/6999146.html

接下来就开始暴躁地推式子了：

$Ans=\sum_{i=1}^n\sum_{j=1}^md(ij)=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[(x,y)=1]$

变更枚举的顺序，先枚举$x,y$，再枚举$x,y$的倍数$i,j$。设$i=ax,j=by$，更换枚举的变量，枚举$x,y,a,b$,有：

$Ans=\sum_{x=1}^n\sum_{y=1}^m\sum_{a=1}^{\lfloor\frac{n}{x} \rfloor}\sum_{b=1}^{\lfloor\frac{m}{y} \rfloor}[(x,y)=1]=\sum_{x=1}^n\sum_{y=1}^m\lfloor \frac{n}{x} \rfloor\lfloor \frac{m}{y} \rfloor[(x,y)=1]$

注意到$[(x,y)=1]$就是$e(gcd(x,y))$，根据$I\bigotimes \mu=e$，进一步推式子：

$Ans=\sum_{x=1}^n\sum_{y=1}^m\lfloor \frac{n}{x} \rfloor\lfloor \frac{m}{y} \rfloor\sum_{d|x,d|y}\mu(d)$

再次变更枚举的顺序，先枚举$d$，再枚举$d$的倍数$x,y$。下面设$N=min(n,m)$。

$Ans=\sum_{d=1}^N\mu(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{n}{id} \rfloor\lfloor \frac{m}{jd} \rfloor=\sum_{d=1}^N\mu(d)\sum_{i=1}^{\lfloor \frac{n}{d} \rfloor}\lfloor \frac{n}{id} \rfloor\sum_{j=1}^{\lfloor \frac{m}{d} \rfloor}\lfloor \frac{m}{jd} \rfloor$

设$sum(n)=\sum_{i=1}^n\lfloor \frac{n}{i} \rfloor$，那么原式就变成了可以接受的形式：

$Ans=\sum_{d=1}^{N}\mu(d)sum(\lfloor \frac{n}{d} \rfloor)sum(\lfloor \frac{m}{d} \rfloor)$

只要预处理出所有$sum$和$\mu$的前缀和，就可以$O(\sqrt N)$求解单次询问了。

对于$sum$的预处理有两种：

一种是对于每个$n$暴力$O(\sqrt n)$求，总时间复杂度是$O(n\sqrt n)$，可以接受，但不够优秀。

另一种可以做到$O(n)$，这是看出来了$sum(n)=\sum_{i=1}^nd(i)$，下面给出这个的两种证明：

第一种：

$sum(n)=\lfloor \frac{n}{1} \rfloor+ \lfloor \frac{n}{2} \rfloor+...+\lfloor \frac{n}{n-1} \rfloor+\lfloor \frac{n}{n} \rfloor$ $sum(n-1)=\lfloor \frac{n-1}{1} \rfloor+ \lfloor \frac{n-1}{2} \rfloor+...+\lfloor \frac{n-1}{n-1} \rfloor$

可以看到，$sum(n)$对于$sum(n-1)$,除了多了一项$\lfloor\frac{n}{n}\rfloor=1$，其他分母相等的项，上面不是与下面相等，就是比下面多1.容易发现上面比下面对应项多1当且仅当分子是$n$的约数。所以有：

$sum(n)=sum(n-1)+\sum_{d|n,d<n}1+1=sum(n-1)+\sum_{d|n}1=sum(n-1)+d(n)$

所以$sum$就是$d$的前缀和。

第二种：

直接猜想$sum$是$d$的前缀和，对$d$的前缀和进行变形。

$\sum_{i=1}^nd(i)=\sum_{i=1}^n\sum_{d|i}1$

这里的$i$一定满足$i=kd,k\in \mathbb{N^*}$，那么采用与杜教筛里类似的方法，枚举这个$k$.

$\sum_{i=1}^nd(i)=\sum_{k=1}^n\sum_{d=1}^{\lfloor \frac{n}{k} \rfloor}1=\sum_{k=1}^n\lfloor\frac{n}{k}\rfloor$

代码等试题解封之后再放吧