题目大意
对于 $n$ 的唯一分解 $n=\prod p^c$，定义 $f(n)=\max\{c\}$。
$T$ 组询问，给定 $n,m$，求
$$
\sum_{i=1}^n\sum_{i=1}^mf(\gcd(i,j))
$$
$T\le 10^4$，$n,m\le 10^7$
Solution
考虑莫比乌斯反演，原式可化为
$$
\sum_{d=1}^nf(d)\sum_{i=1}^{\left\lfloor\frac nd\right\rfloor}\sum_{i=1}^{\left\lfloor\frac md\right\rfloor}[\gcd(i,j)=1]
$$
$$
\sum_{d=1}^nf(d)\sum_{x|d}\mu(x)\left\lfloor\frac {n}{dx}\right\rfloor\left\lfloor\frac {m}{dx}\right\rfloor
$$
$$
\sum_{T=1}^n\left\lfloor\frac nT\right\rfloor\left\lfloor\frac mT\right\rfloor\sum_{d|T}f(d)\mu\left(\frac Td\right)
$$
令
$$
g(n)=\sum_{d|n}f(d)\mu\left(\frac nd\right)
$$
将 $n,d$ 唯一分解 $n=\prod\limits_{i=1}^kp_i^{x_i},d=\prod\limits_{i=1}^kp_i^{y_i}$。则 $\mu\left(\dfrac nd\right)$ 取到非零值当且仅当
$$
\forall i\in[1,k],y_i-x_i\le 1
$$
设 $a=\max\{c_i\}$，则 $f(d)=a$ 或 $f(d)=a-1$。
当 $f(d)=a$ 时，设有 $q$ 个质因数的指数为 $a$，则
$$
g(n)=a\sum_{d|n}\mu\left(\frac nd\right)=a\sum_{i=1}^q\binom{q}{i}(-1)^{q-i}\sum_{j=0}^{k-q}\binom{k-q}{j}(-1)^j
$$
当 $k-q\neq0$，$g(n)=0$。
当 $k-q=0$，即 $k=q$ 时
$$
g(n)=a\sum_{i=1}^k\binom{k}{i}(-1)^{k-i}=a\left(\sum_{i=0}^k\binom{k}{i}(-1)^{k-i}-(-1)^k\right)=(-1)^{k+1}a
$$
当 $f(d)=a-1$ 时，同理得到当 $k-q\neq0$ 时，$g(n)=0$
当 $k-q=0$ 时，$g(n)=(1-a)(-1)^{k+1}$
故
$$
g(n)=\begin{cases}
(-1)^{k+1}&k=q\\
0&k\neq q
\end{cases}
$$
原式
$$
\sum_{T=1}^n\left\lfloor\frac nT\right\rfloor\left\lfloor\frac mT\right\rfloor g(T)
$$
可以数论分块简单解决。
考虑如何筛出 $g$，考虑 $k=q=1$ 的情况，此时与 $\mu$ 类似，可以直接线筛，对于 $k>1$ 的部分可以 $O(n\ln n)$ 小常数枚举。总时间复杂度 $O(n\ln n+T\sqrt n)$。