P3935 Calculating
Statement
若 x 分解质因数结果为 x=p_1^{k_1}p_2^{k_2}\cdots p_n^{k_n}，令 f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)，求 \sum_{i=l}^rf(i) 对 998\,244\,353 取模的结果。
### Solution
首先观察可知
$$
f(x)=d(x)
$$
设
$$
s(x)=\sum\limits_{i=1}^x d(i)
$$
则答案即为
$$
s(r)-s(l-1)
$$
推式子求 $s(x)$：
$$
\begin{aligned}
s(x)&=\sum_{i=1}^x d(i) \\
&=\sum_{i=1}^x\sum_{j=1}^i [j \mid i] \\
&=\sum_{j=1}^x\sum_{i=j}^x [j \mid i] \\
&=\sum_{j=1}^x \left\lfloor \dfrac x j\right\rfloor \\
\end{aligned}
$$
这个式子显然可以用数论分块优化。
时间复杂度 $\mathcal O (\sqrt r)$。
## [P2261 [CQOI2007] 余数求和](https://www.luogu.com.cn/problem/P2261)
### Statement
计算：
$$
G(n,k)=\sum_{i=1}^n k \bmod i
$$
$1 \le n,k \le 10^9$。
### Solution
推式子：
$$
\begin{aligned}
G(n,k)&=\sum_{i=1}^n k \bmod i\\
&= \sum_{i=1}^n k-i\left\lfloor \dfrac k i\right\rfloor\\
&= nk - \sum_{i=1}^n i\left\lfloor \dfrac k i\right\rfloor
\end{aligned}
$$
直接上数论分块优化即可。
时间复杂度 $\mathcal O (\sqrt n)$。
## [CF616E Sum of Remainders](https://www.luogu.com.cn/problem/CF616E)
同 [P2261 [CQOI2007] 余数求和](https://www.luogu.com.cn/problem/P2261)。
## [P2424 约数和](https://www.luogu.com.cn/problem/P2424)
### Statement
定义 $f(x)$ 等于 $x$ 的约数和，求 $\sum\limits_{i=l}^r f(i)$。
$1 \le l \lt r \le 2\times10^9$。
### Solution
设
$$
s(x)=\sum\limits_{i=1}^x f(x)
$$
则答案即为
$$
s(r)-s(l-1)
$$
推式子求 $s(x)$：
$$
\begin{aligned}
s(x)&=\sum_{i=1}^x f(i)\\
&=\sum_{i=1}^x\sum_{d|i} d\\
&=\sum_{d=1}^x d \cdot\sum_{i=1}^x [d \mid i]\\
&=\sum_{d=1}^x d\left\lfloor\dfrac x d\right\rfloor
\end{aligned}
$$
同样上数论分块优化即可。
时间复杂度 $\mathcal O (\sqrt r)$。
## [P2158 [SDOI2008] 仪仗队](https://www.luogu.com.cn/problem/P2158)
### Statement
计算：
$$
\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [\gcd(i,j)=1]
$$
其中，$\gcd(x,0)=x$。
$1 \le n \le 40000$。
### Solution
莫比乌斯反演做法：在特判 $n=1$ 的情况后直接推式子：
$$
\begin{aligned}
\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [\gcd(i,j)=1]
&=2+\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=1]\\
&=2+\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}\varepsilon(\gcd(i,j))\\
&=2+\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}\sum_{d\mid\gcd(i,j)} \mu(d)\\
&=2+\sum_{d=1}^{n-1}\sum_{d\mid i}^{n-1}\sum_{d|j}^{n-1} \mu(d)\\
&=2+\sum_{d=1}^{n-1} \mu(d)\left\lfloor\dfrac {n-1} d\right\rfloor^2
\end{aligned}
$$
线性筛莫比乌斯函数即可，时间复杂度 $\mathcal O(n)$。
欧拉函数做法：同样在特判 $n=1$ 的情况后直接推式子：
$$
\begin{aligned}
\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [\gcd(i,j)=1]
&=2+\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=1]\\
&=1+2\sum_{i=1}^{n-1}\varphi(i)
\end{aligned}
$$
线性筛欧拉函数即可，时间复杂度同样为 $\mathcal O(n)$。
## [P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522)
### Statement
$n$ 组数据，计算：
$$
\sum_{x=a}^b \sum_{y=c}^d [\gcd(x,y)=k]
$$
$1 \le n,k \le 5\times 10^4$，$1 \le a\le b \le 5\times 10^4$，$1 \le c\le d \le 5\times 10^4$。
### Solution
设
$$
f(n,m)=\sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=k]
$$
则根据二维前缀和可知答案即为
$$
f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)
$$
推式子求 $f(n,m)$：
$$
\begin{aligned}
f(n,m) &=\sum_{x=1}^n \sum_{y=1}^m [\gcd(x,y)=k]\\
&=\sum_{x=1}^{\left\lfloor\frac n k\right\rfloor} \sum_{y=1}^{\left\lfloor\frac m k\right\rfloor}[\gcd(x,y)=1]\\
&= \sum_{x=1}^{\left\lfloor\frac n k\right\rfloor} \sum_{y=1}^{\left\lfloor\frac m k\right\rfloor}\varepsilon(\gcd(x,y))
\end{aligned}
$$
设
$$
p=\left\lfloor \dfrac n k \right\rfloor,q=\left\lfloor \dfrac m k \right\rfloor
$$
不妨设 $n \le m$，则 $p \le q$。
可以得到
$$
\begin{aligned}
f(n,m) &= \sum_{x=1}^p \sum_{y=1}^q\varepsilon(\gcd(x,y))\\
&= \sum_{x=1}^p \sum_{y=1}^q \sum_{d \mid \gcd(x,y)} \mu(d)\\
&= \sum_{d=1}^{p}\mu(d) \sum_{x=1}^p[d\mid x] \sum_{y=1}^q[d \mid y]\\
&= \sum_{d=1}^{p}\mu(d) \left\lfloor \dfrac p d\right\rfloor \left\lfloor \dfrac q d\right\rfloor
\end{aligned}
$$
仍然上数论分块优化即可。
时间复杂度 $\mathcal O (V+n \sqrt V)$，其中 $V$ 为值域。
## [P4450 双亲数](https://www.luogu.com.cn/problem/P4450)
[P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522) 弱化版。
## [P3455 [POI2007] ZAP-Queries](https://www.luogu.com.cn/problem/P3455)
同样为 [P2522 [HAOI2011] Problem b](https://www.luogu.com.cn/problem/P2522) 弱化版。
## [P10532 [XJTUPC2024] 筛法](https://www.luogu.com.cn/problem/P10532)
### Statement
计算：
$$
\sum_{i=1}^n\sum_{j=1}^n\left\lfloor\dfrac n {\max(i,j)}\right\rfloor[i \perp j]
$$
其中 $[i \perp j]$ 表示 $i,j$ 是否互素，即当 $\gcd(i,j)=1$ 时，$[i \perp j]$ 的值为 $1$，其余情况其值为 $0$。
$1\le n \le 10^9$。
### Solution
推式子：
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^n\left\lfloor\dfrac n {\max(i,j)}\right\rfloor[i \perp j]
&=-n+2\sum_{i=1}^n\sum_{j=1}^i\left\lfloor\dfrac n {i}\right\rfloor[i \perp j]\\
&=-n+2\sum_{i=1}^n\left\lfloor\dfrac n {i}\right\rfloor\varphi(i)\\
&=-n+2\sum_{i=1}^n\sum_{j=1}^n[i \mid j] \varphi(i)\\
&=-n+2\sum_{i=1}^n\sum_{j=1}^n[j \mid i] \varphi(j)\\
&=-n+2\sum_{i=1}^n\sum_{d \mid i}\varphi(i)\\
&=-n+2\sum_{i=1}^n i\\
&=-n+n(n+1)\\
&=n^2
\end{aligned}
$$
当然，也可以从组合意义理解：
对于原式，我们可以理解为对于每一个满足 $i \perp j$ 且 $1 \le i,j \le n$ 的数对 $(i,j)$，所有满足 $1 \le k \le \dfrac n {\max(i,j)}$ 的数对 $(ik,jk)$ 会被统计入 $(i,j)$ 的答案中。
我们反向考虑这个统计关系：对于每一个满足 $1 \le i,j \le n$ 的数对 $(i,j)$，它会被统计入 $\left(\dfrac i {\gcd(i,j)},\dfrac j {\gcd(i,j)}\right)$ 的答案中。
每一个满足 $1 \le i,j \le n$ 的数对 $(i,j)$ 都会被统计入一次答案，而一共有 $n^2$ 个数对，所以答案即为 $n^2$。
## [P1829 [国家集训队] Crash 的数字表格 / JZPTAB](https://www.luogu.com.cn/problem/P1829)
### Statement
计算：
$$
\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j)
$$
答案对 $20101009$ 取模。
$1 \le n,m \le 10^7$。
### Solution
不妨设 $n \le m$。
推式子：
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j)&=\sum_{i=1}^n\sum_{j=1}^m \dfrac {i\cdot j}{\gcd(i,j)} \\
&=\sum_{d=1}^{n}\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=d]\dfrac{i\cdot j}{d}\\
&=\sum_{d=1}^{n}\sum_{i=1}^{\left\lfloor\frac n d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m d\right\rfloor}[\gcd(i,j)=1]i\cdot j\cdot d\\
&=\sum_{d=1}^{n}d\cdot \sum_{i=1}^{\left\lfloor\frac n d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m d\right\rfloor}[\gcd(i,j)=1]i\cdot j
\end{aligned}
$$
设
$$
f(x,y)=\sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=1]i\cdot j
$$
则
$$
\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j)=\sum_{d=1}^n d\cdot f\left(\left\lfloor\dfrac n d\right\rfloor,\left\lfloor\dfrac m d\right\rfloor\right)
$$
不妨设 $x \le y$，推式子求 $f(x,y)$：
$$
\begin{aligned}
f(x,y)&=\sum_{i=1}^{x}\sum_{j=1}^{y}[\gcd(i,j)=1]i\cdot j\\
&=\sum_{i=1}^x\sum_{j=1}^y\sum_{d\mid\gcd(i,j)} \mu(d)\cdot i\cdot j\\
&=\sum_{d=1}^x \mu(d)\sum_{d\mid i}^x\sum_{d\mid j}^y i\cdot j\\
&=\sum_{d=1}^x \mu(d) \sum_{i=1}^{\left\lfloor \frac x d\right\rfloor}\sum_{j=1}^{\left\lfloor \frac y d\right\rfloor} i \cdot j \cdot d^2\\
&=\sum_{d=1}^x \mu(d)\cdot d^2\cdot \sum_{i=1}^{\left\lfloor \frac x d\right\rfloor}\sum_{j=1}^{\left\lfloor \frac y d\right\rfloor} i \cdot j\\
\end{aligned}
$$
设
$$
g(x,y)=\sum_{i=1}^x \sum_{j=1}^y i\cdot j=\dfrac {x\cdot(x+1)}2\times\dfrac{y\cdot(y+1)} 2
$$
则
$$
f(x,y)=\sum_{d=1}^x \mu(d)\cdot d^2\cdot g\left(\left\lfloor\dfrac x d\right\rfloor,\left\lfloor\dfrac y d \right\rfloor\right)
$$
这个式子中的 $\mu(d)\cdot d^2$ 可以 $\mathcal O(n)$ 预处理 $\mathcal O(1)$ 查询，$g\left(\left\lfloor\dfrac x d\right\rfloor,\left\lfloor\dfrac y d \right\rfloor\right)$ 可以直接 $\mathcal O (1)$ 查询，所以可以对其进行数论分块优化，时间复杂度为 $\mathcal O(\sqrt x)$。
又因为
$$
\sum_{i=1}^n\sum_{j=1}^m \operatorname{lcm}(i,j)=\sum_{d=1}^n d\cdot f\left(\left\lfloor\dfrac n d\right\rfloor,\left\lfloor\dfrac m d\right\rfloor\right)
$$
这个式子仍然可以进行数论分块优化，而 $f(x,y)$ 可以在 $\mathcal O(\sqrt x)$ 的时间复杂度内求解，所以可以做到 $\mathcal O(n^{\frac 3 4})$ 求答案。
总时间复杂度 $\mathcal O(n)$，瓶颈在于预处理。
## [P2257 YY 的 GCD](https://www.luogu.com.cn/problem/P2257)
### Statement
$T$ 组数据，给定 $n,m$，求满足 $1 \le x \le n$，$1 \le y \le m$ 且 $\gcd(x,y)$ 为质数的 $(x,y)$ 有多少对。
$T=10^4$，$1 \le n,m \le 10^7$。
### Solution
不妨设 $n \le m$。
设答案为 $ans$，推式子：
$$
\begin{aligned}
ans&= \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in \mathbb P]\\
&=\sum_{p\in\mathbb P}^n \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=p]\\
&=\sum_{p\in\mathbb P}^n \sum_{i=1}^{\left\lfloor \frac n p\right\rfloor} \sum_{j=1}^{\left\lfloor \frac m p\right\rfloor} [\gcd(i,j)=1]\\
&=\sum_{p\in\mathbb P}^n \sum_{i=1}^{\left\lfloor \frac n p\right\rfloor} \sum_{j=1}^{\left\lfloor \frac m p\right\rfloor}\sum_{d\mid \gcd(i,j)} \mu(d)\\
&=\sum_{p\in\mathbb P}^n \sum_{d=1}^n\sum_{d \mid i}^{\left\lfloor \frac n p\right\rfloor} \sum_{d \mid j}^{\left\lfloor \frac m p\right\rfloor} \mu(d)\\
&=\sum_{p\in\mathbb P}^n \sum_{d=1}^n\mu(d)\left\lfloor \frac n {dp}\right\rfloor\left\lfloor \frac m {dp}\right\rfloor\\
&=\sum_{k=1}^n\sum_{p \in \mathbb P,p \mid k}^n \mu\left(\dfrac k p\right)\left\lfloor \frac n k\right\rfloor\left\lfloor \frac m k\right\rfloor\\
&=\sum_{k=1}^n\left\lfloor \frac n k\right\rfloor\left\lfloor \frac m k\right\rfloor\sum_{p \in \mathbb P,p \mid k}^n \mu\left(\dfrac k p\right)
\end{aligned}
$$
设
$$
f(k)=\sum_{p \in \mathbb P,p \mid k}^n \mu\left(\dfrac k p\right)
$$
则
$$
ans=\sum_{k=1}^n\left\lfloor \frac n k\right\rfloor\left\lfloor \frac m k\right\rfloor f(k)
$$
容易发现，可以 $\mathcal O(n \log \log n)$ 地预处理出 $f(k)$ 的值，于是可以对这个式子进行数论分块优化，做到 $\mathcal O(\sqrt n)$ 回答单次询问。
总时间复杂度 $\mathcal O(n \log \log n+T\sqrt n)$。
## [P3327 [SDOI2015] 约数个数和](https://www.luogu.com.cn/problem/P3327)
### Statement
$T$ 组数据，计算：
$$
\sum_{i=1}^n\sum_{j=1}^m d(ij)
$$
$1 \le T,n,m \le 50000$。
### Solution
引理：
$$
d(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]
$$
可以通过将 $i,j$ 分解质因数的方式证明左式与右式相等。
回到原式。不妨设 $n \le m$。
推式子：
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^m d(ij)
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}\sum_{g \mid \gcd(x,y)} \mu(g)\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{g\mid\gcd(i,j)}\sum_{g\mid x,x\mid i}\sum_{g\mid y,y\mid j}\mu(g)\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{g\mid\gcd(i,j)} d\left(\left\lfloor\dfrac i g\right\rfloor\right)d\left(\left\lfloor\dfrac j g\right\rfloor\right)\mu(g)\\
&=\sum_{g=1}^n\sum_{g\mid i}^n\sum_{g\mid j}^m\ d\left(\left\lfloor\dfrac i g\right\rfloor\right)d\left(\left\lfloor\dfrac j g\right\rfloor\right)\mu(g)\\
&=\sum_{g=1}^n\mu(g)\sum_{i=1}^{\left\lfloor\frac n g\right\rfloor}d(i)\sum_{j=1}^{\left\lfloor\frac m g\right\rfloor}d(j)\\
\end{aligned}
$$
设
$$
f(k)=\sum_{i=1}^k d(i)
$$
则
$$
\sum_{i=1}^n\sum_{j=1}^m d(ij)=\sum_{g=1}^n\mu(g)\cdot f\left(\left\lfloor\frac n g\right\rfloor\right)\cdot f\left(\left\lfloor\frac m g\right\rfloor\right)
$$
直接预处理出 $f(k)$ 的值并对这个式子进行数论分块优化即可。
时间复杂度 $\mathcal O(n+T\sqrt n)$。
还有另外一种推式子方式：
$$
\begin{aligned}
\sum_{i=1}^n\sum_{j=1}^m d(ij)
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]\\
&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}\sum_{g \mid \gcd(x,y)} \mu(g)\\
&=\sum_{x=1}^n\sum_{y=1}^m\sum_{x\mid i}^n\sum_{y\mid j}^m\sum_{g \mid \gcd(x,y)} \mu(g)\\
&=\sum_{x=1}^n\sum_{y=1}^m\left\lfloor\dfrac n x\right\rfloor\left\lfloor\dfrac m y\right\rfloor\sum_{g \mid \gcd(x,y)} \mu(g)\\
&=\sum_{g=1}^n\sum_{g\mid x}^n\sum_{g\mid y}^m\left\lfloor\dfrac n x\right\rfloor\left\lfloor\dfrac m y\right\rfloor \mu(g)\\
&=\sum_{g=1}^n\mu(g)\sum_{x=1}^{\left\lfloor\frac n g\right\rfloor}\left\lfloor\dfrac n {gx}\right\rfloor\sum_{y=1}^{\left\lfloor\frac m g\right\rfloor}\left\lfloor\dfrac m {gy}\right\rfloor\\
\end{aligned}
$$
设
$$
f(k)=\sum_{i=1}^k\left\lfloor\dfrac k i\right\rfloor
$$
则
$$
\sum_{i=1}^n\sum_{j=1}^m d(ij)=\sum_{g=1}^n\mu(g)\cdot f\left(\left\lfloor\frac n g\right\rfloor\right)\cdot f\left(\left\lfloor\frac m g\right\rfloor\right)
$$
同样预处理出 $f(k)$ 的值并对这个式子进行数论分块优化即可。
时间复杂度 $\mathcal O(n\sqrt n+T\sqrt n)$。
当然，由于
$$
f(k)=\sum_{i=1}^n \left\lfloor \dfrac k i\right\rfloor=\sum_{i=1}^n d(i)
$$
这里可以转化为求 $d(i)$ 的值，即第一种计算方式，做到 $\mathcal O(n+T\sqrt n)$ 的时间复杂度。
## [P3704 [SDOI2017] 数字表格](https://www.luogu.com.cn/problem/P3704)
### Statement
$T$ 组数据，设 $f_i$ 表示斐波那契数列的第 $i$ 项，计算：
$$
\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)}
$$
答案对 $10^9+7$ 取模。
$1 \le T\le 10^3$，$1\le n,m \le 10^6$。
### Solution
不妨设 $n \le m$。
设
$$
c(k)=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]
$$
则
$$
\prod_{i=1}^n\prod_{j=1}^m f_{\gcd(i,j)}=\prod_{i=1}^n {f_i}^{c(i)}
$$
推式子求 $c(k)$：
$$
\begin{aligned}
c(k)&=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=k]\\
&=\sum_{i=1}^{\left\lfloor\frac n k\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m k\right\rfloor} [\gcd(i,j)=1]\\
&=\sum_{i=1}^{\left\lfloor\frac n k\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m k\right\rfloor} \sum_{d \mid \gcd(i,j)}\mu(d)\\
&=\sum_{d=1}^n\sum_{d\mid i}^{\left\lfloor\frac n k\right\rfloor}\sum_{d\mid j}^{\left\lfloor\frac m k\right\rfloor}\mu(d)\\
&=\sum_{d=1}^n\mu(d)\left\lfloor\dfrac n {dk}\right\rfloor\left\lfloor\dfrac m {dk}\right\rfloor\\
\end{aligned}
$$
容易发现，$c(k)$ 和原式都可以进行数论分块优化，于是可以使用数论分块套数论分块，做到 $\mathcal O(n \log M)$ 预处理，$\mathcal O(n^{\frac 3 4}+\sqrt n\log M)$ 回答单次询问，其中 $M$ 表示模数，即 $10^9+7$。
总时间复杂度 $\mathcal O(n \log M+Tn^{\frac 3 4}+T\sqrt n\log M)$。记得对指数取模的时候模数是 $M-1$。
还有一种复杂度更低的方法，之后写。咕咕咕。
## [P3312 [SDOI2014] 数表](https://www.luogu.com.cn/problem/P3312)
### Statement
$Q$ 组数据，计算：
$$
\sum_{i=1}^n\sum_{j=1}^m [\sigma_1(\gcd(i,j)) \le a]\cdot \sigma_1(\gcd(i,j))
$$
$1 \le Q \le 2\times10^4$，$1\le n,m \le 10^5$，$|a| \le 10^9$。
### Solution
不妨设 $n \le m$。
设答案为 $ans$，推式子：
$$
\begin{aligned}
ans
&=\sum_{i=1}^n\sum_{j=1}^m [\sigma_1(\gcd(i,j)) \le a]\cdot \sigma_1(\gcd(i,j))\\
&=\sum_{d=1}^n[\sigma_1(d)\le a]\cdot\sigma_1(d)\cdot\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d] \\
&=\sum_{d=1}^n[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\sum_{i=1}^{\left\lfloor\frac n d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m d\right\rfloor}[\gcd(i,j)=1]\\
&=\sum_{d=1}^n[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\sum_{i=1}^{\left\lfloor\frac n d\right\rfloor}\sum_{j=1}^{\left\lfloor\frac m d\right\rfloor}\sum_{g\mid \gcd(i,j)} \mu(p)\\
&=\sum_{d=1}^n[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\sum_{g=1}^n\sum_{g\mid i}^{\left\lfloor\frac n d\right\rfloor}\sum_{g\mid j}^{\left\lfloor\frac m d\right\rfloor}\mu(g)\\
&=\sum_{d=1}^n[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\sum_{p=1}^n\mu(g)\left\lfloor\dfrac n {dg}\right\rfloor\left\lfloor\dfrac m {dg}\right\rfloor\\
&=\sum_{p=1}^n\sum_{d\mid p}[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\mu\left(\dfrac p d\right)\left\lfloor\dfrac n p\right\rfloor\left\lfloor\dfrac m p\right\rfloor\\
\end{aligned}
$$
设
$$
f(p)=\sum_{d\mid p}[\sigma_1(d)\le a]\cdot \sigma_1(d)\cdot\mu\left(\dfrac p d\right)\\
s(p)=\sum_{i=1}^p f(i)
$$
则
$$
ans=\sum_{p=1}^nf(p)\left\lfloor\dfrac n p\right\rfloor\left\lfloor\dfrac m p\right\rfloor\\
$$
此时我们只需要维护 $s(p)$ 的值即可使用数论分块求解答案。
考虑将所有询问按照 $a$ 从小到大排序，使用一棵线段树动态维护 $s(p)$ 的值。
具体维护过程是，在求排序后第 $i$ 个询问的答案前，对于所有满足 $a_{i-1} \le \sigma_1(d) \le a_i$ 的不大于 $n$ 的正整数 $d$ 和所有不大于 $\left\lfloor \dfrac n d\right\rfloor$ 的正整数 $k$ ，将 $s(kd)$ 到 $s(n)$ 的值增加 $\sigma_1(d) \cdot \mu(k)$，其中 $\sigma_1(d)$ 和 $\mu(k)$ 可以用线性筛预处理出。
显然，这样维护的时间复杂度是调和级数与线段树的 $\log$ 的乘积，即 $\mathcal O(n \log^2 n)$。
于是每次询问就可以进行数论分块优化了，回答单次询问的时间复杂度为 $\mathcal O(\sqrt n \log n)$。
总时间复杂度 $\mathcal O(Q \log Q+n \log^2 n+Q\sqrt n \log n)$。